求最长不下降序列
-
总时间限制:
- 2000ms 内存限制:
- 65536kB
-
描述
-
一个数的序列
bi，当
b1 <=
b2 < =... < =
bS的时候，我们称这个序列是不下降的。对于给定的一个序列(
a1,
a2, ...,
aN)，我们可以得到一些不下降的子序列(
ai1,
ai2, ...,
aiK)，这里1 <=
i1 <
i2 < ... <
iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些不下降子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).
你的任务，就是对于给定的序列，求出最长不下降子序列的长度。 输入
- 输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。 输出
- 最长不下降序列的长度。 样例输入
-
7 1 7 3 5 9 4 8
样例输出
-
4
来源
- 翻译自 Northeastern Europe 2002, Far-Eastern Subregion 的比赛试题
-
- 【解析】
- 同学们看到这道题，不用说，一定使用动态规划来做，那怎么做呢？
- 状态: Accepted
//求最长不下降子序列 #include<cstdio> #include<cstring> int y,c; int a[200][10]; int main() {int n;scanf("%d",&n);for(int l=1;l<=n;l++){scanf("%d",&a[l][1]);a[l][2]=1;//初始长度都为1a[l][3]=0;}for(int l=n-1;l>=1;l--){y=0;c=0;//注意每次都要清零for(int j=l+1;j<=n;j++) {if(a[j][1]>a[l][1]&&(a[j][2]>y))//最后一句话不能省{y=a[j][2];//最大长度c=j;}if(y>0){a[l][2]=y+1;//a[l][2]=a[j][2]+1这样也行吗？当然不行！当a[j][1]在第一个if中不满足条件时，y就不会改变，但如果用a[j][2]则是要改变的。a[l][3]=c;}}}c=1;for(int j=1;j<=n;j++)if(a[j][2]>a[c][2]) c=j;printf("%d\n",a[c][2]);//最大的长度while(c!=0){printf("%d ",a[c][1]);c=a[c][3]; } }
- 状态: Accepted
-
全局题号
- 1759 添加于
- 2015-11-03 提交次数
- 9424 尝试人数
- 3248 通过人数
- 2945
你的提交记录
| # | 结果 | 时间 |
| 2 | Accepted | 07-05 |
| 1 | Accepted | 02-23 |