Loading... # 题目描述 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 # 输入格式 一行，若干个整数，中间由空格隔开。 # 输出格式 两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 # 解题思路 ## 最多可以拦截多少导弹 这个问题是一道裸的最长不上升子序列问题， 直接使用最长上升子序列就可以解决 ## 需要配备多少套拦截系统 对于这个问题可以采用贪心策略进行优化： - 朴素的想法是每次对于没有拦截的导弹计算一次最长不上升子序列 - 考虑用贪心策略优化 - 设`res[j]`是第`j`个最长不上升子序列的最后一个元素， 对于当前的导弹`a[i]` - 如果有`res[j]>=a[i]`则可以拦截， 将他归到当前队伍的队尾， - 否则查找`k=j+1`是否可以拦截 - 如果都不可以拦截自成一队 # AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #define endl '\n' using namespace std; const int N = 1010; int n; int a[N]; int idx = 1; int dp[N]; vector<int> res[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; while(cin >> t) { a[idx] = t; idx ++; } n = idx - 1; int ans = 0; for(int i = 1; i <= n; i ++) { dp[i] = 1; for(int j = 1; j < i; j ++) { if(a[j] >= a[i]) dp[i] = max(dp[i], dp[j] + 1); } ans = max(ans, dp[i]); } cout << ans << endl; ans = 0, idx = 0; for(int i = 1; i <= n; i ++) { bool flag = true; for(int j = 0; j < idx; j ++) { if(res[idx].size() && res[idx].back() >= a[i]) { res[idx].push_back(a[i]); flag = false; break; } } if(flag) { idx ++; res[idx].push_back(a[i]); } } cout << idx << endl; return 0; } ``` 最后修改：2025 年 01 月 15 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏