由n个整数组成的数列,记为b[1], b[2], …, b[n]。若存在i1 b[i2]> … >b[ie]则称为长度为e的下降子序列。求最长下降子序列(Longest decreasing subsequence, LDS) 输入输出格式 输入格式 输入格式: 一行,整数序列,长度未知. 序列长度<=100000, 每个整数绝对值<=10000 输出格式 输出格式: 一个正整数
时间: 2023-12-16 08:06:45 浏览: 36
这是一个典型的动态规划问题。可以用一个数组dp来存储以每一个数为结尾的最长下降子序列的长度,初始值为1,因为每个数本身都可以看做是一个长度为1的下降子序列。然后从左到右遍历整个数列,对于每一个数b[i],在它左边的所有数b[j],如果b[j]>b[i],那么以b[j]为结尾的最长下降子序列长度dp[j]+1就可以更新以b[i]为结尾的最长下降子序列长度dp[i]了。最后dp数组中的最大值即为所求的最长下降子序列长度。下面是代码实现:
```python
n = int(input())
a = list(map(int, input().split()))
dp = [1] * n
for i in range(1, n):
for j in range(i):
if a[j] > a[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
```
复杂度为O(n^2),可以通过本题。
相关问题
1^b+2^b+3^b+...+n^b数列
这个数列是一个特殊的数学序列,其中每一项都是一个数字的幂次方之和。具体来说,数列的第n项可以表示为1^b + 2^b + 3^b + ... + n^b,其中b是一个常数。
这个数列在数学中没有一个通用的封闭形式的表达式,也就是没有一个简单的公式可以直接计算出数列的值。但是,我们可以通过迭代的方式来计算数列的部分和。
下面是一个示例的算法来计算数列的部分和:
1. 初始化部分和sum为0。
2. 对于每一个从1到n的整数i,计算i的b次方,并将结果加到sum中。
3. 返回sum作为数列的部分和。
请注意,这个算法的时间复杂度是O(n),因为需要对每一个从1到n的整数进行计算。如果n很大,计算时间可能会比较长。
C语言自动生成[a, b]范围之内的n个整数
可以使用rand()函数生成随机数,结合循环语句生成n个整数。具体代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
int a, b, n, i;
srand(time(NULL)); // 设置随机数种子为当前时间
printf("请输入范围[a, b]和要生成的整数个数n:");
scanf("%d%d%d", &a, &b, &n);
for (i = 1; i <= n; i++) {
printf("%d ", rand() % (b - a + 1) + a); // 生成[a, b]范围内的随机数
}
return 0;
}
```
在程序中,我们使用srand()函数设置随机数种子为当前时间,确保每次运行程序生成的随机数不同。然后使用rand()函数生成一个随机数,再通过取模运算和加法运算得到[a, b]范围内的随机数。最后使用循环语句生成n个随机数并输出。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)