DP 水题 最长不下降子序列

给一个数组a1, a2 ... an，找到最长的不下降子序列ab1<=ab2<= .. <=abk，其中b1<b2<..bk。

输出长度即可。

第一行，一个整数N。

第二行 ，N个整数（N < = 5000）

输出K的极大值，即最长不下降子序列的长度

5

9 3 6 2 7

3

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include<cstdio> #include<iostream> using namespace std; int n,a[5010]= {0},b[5010]= {0},maxb=0;   int main() {     scanf("%d", &n);     for(int i=1; i<=n; i++)     {         scanf("%d", &a[i]);     }     for(int i=1; i<=n; i++)         for(int j=1; j<i; j++)         {             if(a[i]>=a[j]) b[i]=max(b[i],b[j]+1);         }     for(int i=1; i<=n; i++)     {         maxb=max(maxb,b[i]);     }     printf("%d", maxb+1);     return 0; }

　　

DP 水题 最长不下降子序列,布布扣,bubuko.com

DP 水题 最长不下降子序列

原文：http://www.cnblogs.com/castledrv/p/3653000.html