JDOJ 1929: 求最长不下降序列长度

JDOJ传送门

Description

设有一个正整数的序列：b1,b2,…，bn，对于下标i1<i2<…＜im，若有bi1≤bi2≤…≤bim
则称存在一个长度为m的不下降序列。

现在有n个数，请你求出这n个数的最长不下降序列的长度

Input

第一行为一个整数n （n < 104）

第二行有n个整数，数与数之间使用空格间隔

Output

输出一行，一个整数，最长不下降序列的长度

Sample Input

14 13 7 9 16 38 24 37 18 44 19 21 22 63 15

Sample Output

HINT

样例解释：

最长的不下降序列

7<9<16<18<19<21<22<63

题解：

最长不降子序列问题是线性动归的基础题。

因为它很基础，所以我在这里详讲一下。

我们的最长不降子序列的选择并不一定是连续的，这是这个问题的求解基础。也就是说，我们在进行判断是否进行动归的时候，需要从头再扫描，对枚举到的元素之前的每一个元素进行遍历动归。

可能会比较抽象，但是代码还是比较好实现的，没有看懂讲解的可以结合代码理解。

求解最长不降子序列问题的这种(O(n^2))的做法在一些题目中会被卡数据范围。所以我们又有了二分优化及一些其他的优化方式，在这里就不详细介绍，请有兴趣有能力的同学们自行查阅。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e4+10;
int n,ans;
int a[maxn],dp[maxn];//dp[i]表示以i结尾的最长不降序列长度
//dp[i]=max(dp[j]+1);
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
            if(a[j]<=a[i])
                dp[i]=max(dp[i],dp[j]+1);
        ans=max(ans,dp[i]);
    }
    printf("%d",ans);
    return 0;
}