voip
风的方向
厚德致远,博学敦行!
posts - 52,comments - 21,trackbacks - 0

最长不下降序列

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 阅读(898) 评论(0)  编辑 收藏 引用 所属分类: Questions

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


哈哈哈哈哈哈