希望的海洋

Ain't about how fast I get there,ain't about what's waiting on the other side

常用链接

统计

最新评论

简易DP——最长上升子序列 poj 2533

//状态为数组第位置k，作为每个子序列的末位，状态值为最长上升子序列长度，初始L[0]=1
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>

int k,n,ct,arr[1010],L[1010];


int main()
{
    int i,j,max;
    scanf("%d",&n);
    for(i=0;i<n;++i)
        scanf("%d",&arr[i]);
    L[0]=1;
    for(i=1;i<n;++i)
    {
        max=0;
        for(j=0;j<i;++j)
            if(arr[j]<arr[i]&&L[j]>max)max=L[j];
        L[i]=max+1;
    }
    max=0;
    for(i=0;i<n;++i)//此循环不可少，因为L[n-1]为包含最后一个数字的最大串长度，题目未加此条件
        if(max<L[i])max=L[i];
    printf("%d\n",max);
    return 0;
}

posted on 2011-08-04 19:35 拥梦的小鱼 阅读(496) 评论(0)  编辑 收藏 引用 所属分类: POJ


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