DP专题之LIS(Longest Increasing Subsequence)

 1 /*
 2     LIS(Longest Increasing Subsequence)裸题：
 3         状态转移方程：dp[i] = max (do[i], dp[j] + 1)   (1 <= j < i)
 4         附带有print输出路径函数
 5 */
 6 #include <cstdio>
 7 #include <algorithm>
 8 #include <cstring>
 9 using namespace std;
10 
11 const int MAXN = 1e3 + 10;
12 int a[MAXN];
13 int dp[MAXN];
14 int rt[MAXN];
15 
16 void print(int id, int n)
17 {
18     if (rt[id] != -1)
19     {
20         print (rt[id], n);
21     }
22     printf ("%d%c", a[id], (id == n) ? ‘\n‘ : ‘ ‘);
23 }
24 
25 int main(void)      //POJ 2533 Longest Ordered Subsequence
26 {
27     //freopen ("LIS.in", "r", stdin);
28 
29     int n;
30     scanf ("%d", &n);
31     for (int i=1; i<=n; ++i)
32     {
33         scanf ("%d", &a[i]);
34     }
35 
36     int res = 0;
37     for (int i=1; i<=n; ++i)
38     {
39         dp[i] = 1;  rt[i] = -1;
40         for (int j=1; j<i; ++j)
41         {
42             if (a[j] < a[i])
43             {
44                 if (dp[i] < dp[j] + 1)
45                 {
46                     dp[i] = dp[j] + 1;
47                     rt[i] = j;
48                 }
49             }
50         }
51         res = max (res, dp[i]);
52     }
53 
54     printf ("%d\n", res);
55     //print (n, n);
56 
57     return 0;
58 }