OpenJudge Bailian 2757 最长上升子序列 DP-白红宇

OpenJudge Bailian 2757 最长上升子序列 DP

阅读量：7063 次

发布时间：2019-06-28

本文共 1389 字，大约阅读时间需要 4 分钟。

最长上升子序列

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

Description

一个数的序列

b_i，当

b₁ <

b₂ < ... <

b_S的时候，我们称这个序列是上升的。对于给定的一个序列(

a₁,

a₂, ...,

a_N)，我们可以得到一些上升的子序列(

a_i₁,

a_i₂, ...,

a_{i_K})，这里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

71 7 3 5 9 4 8

Sample Output

#include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 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|1typedef long long LL;typedef pair
                  
                    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]);}