最長不下降序列
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 閱讀(987)
評論(0) 編輯 收藏 引用 所屬分類:
Questions