首页 > 代码库 > HDU 1257 最少拦截系统

HDU 1257 最少拦截系统

2024-07-13 08:37:18   218人阅读

最长递增子序列？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 LOCAL15         freopen("1257in.txt", "r", stdin);16     #endif17 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\n", 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 LOCAL13         freopen("1257in.txt", "r", stdin);14     #endif15 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\n", m);38     }39     return 0;40 }
代码君


联系
我们