tyvj 1049 最长不下降子序列 n^2/nlogn

P1049 最长不下降子序列

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

描述

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

输入格式

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

输出格式

最长不下降子序列的长度

测试样例1

输入

3
1 2 3

输出

3

备注

N小于5000
for each num <=maxint

题意：中文题意

题解：不下降也就是>=

n^n dp[i] 表示以a[i]结尾的最长不下降子序列的长度

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 //#include<bits/stdc++.h>
 8 #include<iostream>
 9 #include<cstring>
10 #include<cstdio>
11 #include<map>
12 #include<algorithm>
13 #include<cmath>
14 #define ll long long
15 #define PI acos(-1.0)
16 #define mod 1000000007
17 using namespace std;
18 int n;
19 int a[5005];
20 int dp[5005];
21 int main()
22 {
23     while(~scanf("%d",&n)){
24     memset(dp,0,sizeof(dp));
25     for(int i=1;i<=n;i++)
26         {
27             scanf("%d",&a[i]);
28             dp[i]=1;
29         }
30     int maxn=1;
31     int ans=0;
32     for(int i=1;i<=n;i++)
33     {
34         maxn=1;
35         for(int j=1;j<i;j++)
36         {
37             if(a[j]<=a[i]&&dp[j]+1>maxn)
38                 maxn=dp[j]+1;
39         }
40         dp[i]=maxn;
41         ans=max(ans,maxn);
42     }
43     cout<<ans;
44     }
45     return 0;
46 }

nlogn 使用upper_bound 与最长上升子序列不同注意边界判断

ans[i] 表示长度为i的最长的不下降的最后一位的值

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 //#include<bits/stdc++.h>
 8 #include<iostream>
 9 #include<cstring>
10 #include<cstdio>
11 #include<map>
12 #include<algorithm>
13 #include<cmath>
14 #define ll long long
15 #define PI acos(-1.0)
16 #define mod 1000000007
17 using namespace std;
18 int n;
19 int a[5005];
20 int main()
21 {
22     while(~scanf("%d",&n)){
23     memset(dp,0,sizeof(dp));
24     for(int i=0;i<n;i++)
25             scanf("%d",&a[i]);
26     int maxn=1;
27     int ans[5005];
28     int top=1;
29     ans[1]=a[0];
30     for(int i=1;i<n;i++)
31     {
32        if(a[i]>=ans[top])
33          ans[++top]=a[i];
34        else
35        {
36            int pos=upper_bound(ans,ans+top,a[i])-ans;//指向大于a[i]的第一个元素的位置
37            ans[pos]=a[i];//更新
38        }
39     }
40     cout<<top<<endl;;
41     }
42     return 0;
43 }