OpenJudge Bailian 2757 最长上升子序列 DP

最长上升子序列

Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

 OpenJ_Bailian 2757

 

Description

一个数的序列 b_i，当 b₁ < b₂ < ... < b_S的时候，我们称这个序列是上升的。对于给定的一个序列( a₁, a₂, ..., a_N)，我们可以得到一些上升的子序列( a_i1, a_i2, ..., a_iK)，这里1 <= i₁ < i₂ < ... < i_K <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

Input

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

Output

最长上升子序列的长度。

Sample Input

7
1 7 3 5 9 4 8

Sample Output

4

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;
#define FIN     freopen("input.txt","r",stdin);
#define FOUT    freopen("output.txt","w",stdout);
#define INF     0x3f3f3f3f
#define INFLL   0x3f3f3f3f3f3f3f
#define lson    l,m,rt<<1
#define rson    m+1,r,rt<<1|1
typedef long long LL;
typedef pair<int,int> PII;

int a[1005];
int dp[1005];

int main()
{
    //FIN
    int n;
    scanf("%d", &n);
    int m;
    dp[1] = 1;
    for(int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    for(int i = 2; i <= n;i ++){
        m = 0;
        for(int j = 1; j <= i-1; j ++){
            if(a[j] < a[i] && dp[j] > m){  //在前i-1中，找出终点小于dp[i]的最长的子序列
                m = dp[j];
            }
        }
        dp[i] = m + 1;
    }
    sort(dp + 1, dp +1 +n);
    printf("%d", dp[n]);

}