LIS HDOJ 1257 最少拦截系统

 1 /*
 2     LIS模板题：n - 最长下降子序列 -> 最长上升子序列　　贪心做法以后再补:)
 3 */
 4 #include <cstdio>
 5 #include <iostream>
 6 #include <cstring>
 7 #include <string>
 8 #include <algorithm>
 9 using namespace std;
10 
11 const int MAXN = 1e4 + 10;
12 const int INF = 0x3f3f3f3f;
13 int a[MAXN];
14 int dp[MAXN];
15 
16 void LIS(int n)
17 {
18     memset (dp, 0, sizeof (dp));
19 
20     int ans = 0;
21     for (int i=1; i<=n; ++i)
22     {
23         dp[i] = 1;
24         for (int j=1; j<i; ++j)
25         {
26             if (a[i] > a[j])
27             {
28                 if (dp[i] < dp[j] + 1)    dp[i] = dp[j] + 1;
29             }
30         }
31         ans = max (ans, dp[i]);
32     }
33 
34     printf ("%d\n", ans);
35 }
36 
37 int main(void)        //HDOJ 1257 最少拦截系统
38 {
39     //freopen ("HDOJ_1257.in", "r", stdin);
40 
41     int n;
42     while (scanf ("%d", &n) == 1)
43     {
44         for (int i=1; i<=n; ++i)    scanf ("%d", &a[i]);
45         LIS (n);
46     }
47 
48     return 0;
49 }