poj2533--Longest Ordered Subsequence(dp: 최장 상승 하위 시퀀스)

Longest Ordered Subsequence
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 33943
 
Accepted: 14871
Description
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

Source
Northeastern Europe 2002, Far-Eastern Subregion
최장 상승 서열을 구합니다:
dp의 구법은 초기화할 때 a[0]를 모든 수보다 작은 값으로 초기화하거나 dp[]를 모두 1로 초기화할 수 있다. 가장 긴 상승자 서열에 자신을 포함하기 때문에 가장 작은 것은 1이다.
 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[12000] , dp[12000] ;
int main()
{
    int i , j , n , max1 ;
    while(scanf("%d", &n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        a[0] = -1 ;
        for(i = 1 ; i <= n ; i++)
            scanf("%d", &a[i]);
        for(i = 1 ; i <= n ; i++)
            for(j = 0 ; j < i ; j++)
                if( a[j] < a[i] && dp[j]+1 > dp[i] )
                    dp[i] = dp[j] + 1 ;
        max1 = 0 ;
        for(i = 1 ; i <= n ; i++)
            max1 = max(max1,dp[i]);
        printf("%d
", max1);
    }
    return 0;
}