POJ 2533 Longest Ordered Subsequence 可以說是非常簡單的dp了

A numeric sequence of  ai is ordered if  a1 <  a2 < ... <  aN. Let the subsequence of the given numeric sequence (  a1,  a2, ...,  aN) be any sequence (  ai1,  ai2, ...,  aiK), where 1 <=  i1 <  i2 < ... <  iK <=  N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8). 

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input

7
1 7 3 5 9 4 8      

Sample Output

4      

求最長遞增子序列的長度，就這樣，嗯。

代碼拿昨天那道跳一跳（位址）改一改就是了，差別一個是狀态轉移方程裡面是dp[j]+1而不是dp[j]+a[i]，另一個是要把dp數組初始化為1，因為第i個數最長遞增子序列最短為1，即隻有它本身。是以dp[i]=max(dp[i],a[i])這條語句也沒有用武之地了。

AC代碼：

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

int main()
{
    int a[1010],dp[1010],n;
    while(cin>>n&&n)
    {
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
            cin>>a[i];
        //dp[0]=a[0];
        for(int i=0;i<n;i++)
            dp[i]=1;
        int maxx=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
                if(a[j]<a[i])
                    dp[i]=max(dp[i],dp[j]+1);
            //dp[i]=max(dp[i],a[i]);
        }
        for(int i=0;i<n;i++)
            maxx=max(maxx,dp[i]);
        cout<<maxx<<endl;
    }
    return 0;
}