最長(zhǎng)不下降序列
Time Limit:1000MS Memory Limit:65536K
Total Submit:488 Accepted:197
Description
有由n個(gè)不相同的整數(shù)組成的數(shù)列，記為a(1)、a(2)、...a(n),當(dāng)i!=j時(shí)，a(i)!=a(j)。若存在i1 < i2 < i3 < ... < ie,且有a(i1) < a(i2) < ... < a(ie), 則稱為長(zhǎng)度為e的不下降序列。
如 3，18，7，14，10，12，23，41，16，24
則有3，18，23，24是一個(gè)長(zhǎng)度為4的不下降子序列
3，7，10，12，23，24是長(zhǎng)度為6的不下降子序列。
現(xiàn)要求你求最長(zhǎng)的不下降子序列。
Input
多組測(cè)試數(shù)據(jù)
每組一行，先輸入一個(gè)數(shù)列長(zhǎng)度n （1 <= n <= 1000),然后是n個(gè)整數(shù)
處理到文件末尾
Output
輸出最長(zhǎng)不下降子序列的長(zhǎng)度
Sample Input
10 3 18 7 14 10 12 23 41 16 24
Sample Output
6
簡(jiǎn)單動(dòng)態(tài)規(guī)劃題，給予我們一種思想！！
代碼如下：
#include<stdio.h>
int Longest_Increasing(int num[],int List[],int n)//List[i]為包含i項(xiàng)在內(nèi)的最長(zhǎng)不下降子序列
{
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("最優(yōu)解：\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 閱讀(995)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Questions