codevs 1576 最长严格上升子序列

1576 最长严格上升子序列

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 黄金 Gold

题目描述 Description

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

输出长度即可。

输入描述 Input Description

第一行，一个整数N。

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

输出描述 Output Description

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

样例输入 Sample Input

9 3 6 2 7

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【样例解释】

最长不下降子序列为3,6,7

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int N=60;
 5 int f[N],a[N];
 6 int main()
 7 {
 8     int n;
 9     scanf("%d",&n);
10     for(int i=1;i<=n;i++){
11         scanf("%d",a+i);
12     }
13     int now,c;
14     f[1]=1;
15     int ans=-1;
16     bool flag=false;
17     for(int i=2;i<=n;i++)
18     {
19         now=-1;
20         c=1;
21         flag=false;
22         for(int j=1;j<=i-1;j++)
23         {
24              if(a[i]>a[j]&&f[j]>now)
25             {
26                 now=f[j];
27                 c=j;
28                 flag=true;
29             }
30         }
31         if(flag)
32         f[i]=f[c]+1;
33         else f[i]=1;
34         if(f[i]>ans)
35         ans=f[i];
36     }
37     printf("%d
",ans);
38     return 0;
39 }