最长不下降序列
Time Limit:1000MS Memory Limit:65536K
Total Submit:488 Accepted:197
Description
有由n个不相同的整数组成的数列，记为a(1)、a(2)、...a(n),当i!=j时，a(i)!=a(j)。若存在i1 < i2 < i3 < ... < ie,且有a(i1) < a(i2) < ... < a(ie), 则称为长度为e的不下降序列。
如 3，18，7，14，10，12，23，41，16，24
则有3，18，23，24是一个长度为4的不下降子序列
3，7，10，12，23，24是长度为6的不下降子序列。
现要求你求最长的不下降子序列。
Input
多组测试数据
每组一行，先输入一个数列长度n （1 <= n <= 1000),然后是n个整数
处理到文件末尾
Output
输出最长不下降子序列的长度
Sample Input
10 3 18 7 14 10 12 23 41 16 24
Sample Output
6
简单动态规划题，给予我们一种思想！！
代码如下：
#include<stdio.h>
int Longest_Increasing(int num[],int List[],int n)//List[i]为包含i项在内的最长不下降子序列
{
int i,j;
for(i=1;i<n;i++)
{
for(j=0;j<i;j++)
{
if(num[i]>num[j]&&List[i]<List[j]+1)
List[i]=List[j]+1;
}
}
return 0;
}
int main()
{
int n,i,ans;
int num[1001],List[1001];
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
List[i]=1;
scanf("%d",&num[i]);
}
Longest_Increasing(num,List,n);
/**//* printf("最优解：\n");
for(i=0;i<n;i++)
printf("%d ",List[i]);
printf("\n");*/
ans=0;
for(i=0;i<n;i++)
if(List[i]>ans)
ans=List[i];
printf("%d\n",ans);
}
return 0;
}
posted on 2010-09-16 13:16
jince 阅读(967)
评论(0) 编辑 收藏 引用 所属分类:
Questions