HDU 1257 最少拦截系统（最长递减子序列的条数）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1257

题解：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 const int maxn = 1000 + 10;
 6 
 7 int dp[maxn],arr[maxn];
 8 int n;
 9 
10 int main() {
11     while (scanf("%d", &n) == 1 && n) {
12         for (int i = 0; i < n; i++) {
13             scanf("%d", arr + i);
14         }
15         int ans = 0;
16         dp[ans++] = arr[0];
17         for (int i = 1; i < n; i++) {
18             int su = 0;
19             //dp数组是递增的！
20             for (int j = 0; j < ans; j++) {
21                 if (dp[j] >= arr[i]) {
22                     dp[j] = arr[i];
23                     su = 1; break;
24                 }
25             }
26             if (!su) {
27                 dp[ans++] = arr[i];
28             }
29         }
30         printf("%d
", ans);
31     }
32     return 0;
33 }