POJ2533:Longest Ordered Subsequence

Longest Ordered Subsequence

Description

Input

Output

Sample Input

7
1 7 3 5 9 4 8

Sample Output

4

这是一道动归题。

n=3

最后找出最大值然后加一；

具体实现如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

const int M = 1000+5;
int sequence[M];    //输入的数据
int dp[M];          

int main()
{
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        for(int i=1; i<=n; i++)
            scanf("%d",  &sequence[i]);
        memset(dp, 0, sizeof(dp));          //初始化为0
        for(int i=1; i<=n; i++)
            for(int j=1; j<i; j++)
            {
                if(sequence[i]>sequence[j])
                    dp[i] = max(dp[i], dp[j] + 1);    //动归方程
            }
        int ans=0;
        for(int i=1; i<=n; i++)
            ans = max(ans, dp[i]);
        printf("%d\n", ans+1);
    }
    return 0;
}

POJ2533:Longest Ordered Subsequence,布布扣,bubuko.com

POJ2533:Longest Ordered Subsequence

原文：http://blog.csdn.net/u013487051/article/details/37052385