【tyvj】P1049 最长不下降子序列

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

求最长不下降子序列的长度

输入格式

第一行为n，表示n个数第二行n个数

输出格式

最长不下降子序列的长度

测试样例1

输入

1 2 3

输出

备注

N小于5000

for each num <=maxint

我们弄一个数组f[i]表示前i个数的最长长度，一开始全都置为1是他自己本身。然后先对0~n-1循环。i =0 ~ n-1对于每一个a[i]在他后面的数设为a[j] (j>i)

如果a[j]>a[i]那说明是有可能被算成最长子序列的。

此时对于a[i]而言无非两种情况，一种是跟着j混，一种是不跟。所以f[j]=max(f[i]+1,f[j])

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int main()

 {

     int n,max=;

     cin>>n;

     int f[],a[];

     for (int i=; i<n; ++i)

         cin>>a[i];

     for (int i=;i<n;++i)

         f[i]=;

     for (int i=; i<n-; ++i) {

         for (int j=i+;j<n;++j)

             if (a[j]>=a[i]&&f[i]+>f[j])

                 f[j]=f[i]+;

     }

     for (int i=; i<n; ++i)

         if (max<f[i])

             max=f[i];

     cout<<max<<endl;

     return ;

 }

秒客网

【tyvj】P1049 最长不下降子序列

相关文章