HDU 1257 最少拦截系统

最长递增子序列？Why？

朦朦胧胧的感觉也许是这样的。。

大神说要用Dilworth定理来证明

无爱了，这个定理先放一放吧

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 1010;
 9 int dp[maxn];
10 int a[maxn];
11 
12 int main(void)
13 {
14     #ifdef LOCAL
15         freopen("1257in.txt", "r", stdin);
16     #endif
17 
18     int i, n, j;
19     memset(dp, 0, sizeof(dp));
20     dp[1] = 1;
21     while(scanf("%d", &n) == 1)
22     {
23         for(i = 1; i <= n; ++i)
24         {
25             scanf("%d", &a[i]);
26             dp[i] = 1;    
27         }
28 
29         for(i = 2; i <= n; ++i)
30             for(j = 1; j < i; ++j)
31             {
32                 if(a[j] < a[i])
33                 {
34                     dp[i] = max(dp[i], dp[j]+1);
35                 }
36             }
37 
38         int ans = 0;
39         for(i = 1; i <= n; ++i)
40             ans = max(ans, dp[i]);
41         printf("%d
", ans);
42     }
43     return 0;
44 }

代码君

还是这种算法比较容易理解：

首先有m个拦截系统，dp[i]是第i个系统的上一发导弹的高度。

如果下一个要发射的高度不超过dp[i]，则更新dp[i]的值

否则++m，把这个值放到dp[m]里

BUT，，，

为什么这样算是对的？？

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 int dp[1010];
 8 int a[1010];
 9 
10 int main(void)
11 {
12     #ifdef LOCAL
13         freopen("1257in.txt", "r", stdin);
14     #endif
15 
16     int n;
17     while(scanf("%d", &n) == 1)
18     {
19         int i, m = 0;
20         int input;
21         memset(dp, 0, sizeof(dp));
22         for(i = 0; i < n; ++i)
23         {
24             scanf("%d", &input);
25             int j;
26             for(j = 1; j <= m; ++j)
27             {
28                 if(input <= dp[j])
29                 {
30                     dp[j] = input;
31                     break;
32                 }
33             }
34             if(j > m)
35                 dp[++m] = input;
36         }
37         printf("%d
", m);
38     }
39     return 0;
40 }

代码君