拦截导弹
题目描述
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。
某天,雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,导弹数不超过1000),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
共一行,输入导弹依次飞来的高度。
输出格式
第一行包含一个整数,表示最多能拦截的导弹数。
第二行包含一个整数,表示要拦截所有导弹最少要配备的系统数。
问题分析
第一问
求最多能拦截的导弹数量,其实就是求最长上升子序列问题的变形。
求的是最长下降子序列,且子序列中的元素可以相等。
第二问
采用贪心的策略:
- 情况 1:如果现有的子序列的结尾都小于当前数,则创建新子序列
- 情况 2:存在一些子序列的结尾大于等于当前数,则将当前数放到这些子序列中,结尾数最小的子序列后面。
贪心正确性证明
证明:贪心解 >= 最优解
贪心算法得到的系统个数一定大于等于最优解的个数。
证明:贪心解 <= 最优解
假设最优解对应的方案与贪心得到的方案不同,则一定能找到一个数,分配的序列不同。
由于贪心法找的是序列末尾最小的,则必有 a ≤ b ≤ x a \leq b \leq x a≤b≤x
因此我们可以交换贪心解法的x + seq1
序列和最优解的x + seq2
序列,将贪心解法调整成最优解方案,且并没有增加子序列个数。
因此,只要贪心解与最优解不同,我们就可以通过上述的调整,将贪心解调整成最优解,且没有增加序列的个数。贪心解 >= 最优解得证。
综上所述,贪心解 == 最优解
重要性质:
- 最长上升子序列问题和最少覆盖下降子序列问题是对偶问题
- Dilworth定理:偏序集能划分成的最少的全序集个数等于最大反链的元素个数。
程序代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int h[N], f[N], g[N];
int n;
int main()
{
while( cin >> h[n] ) {
n++;
}
// 第一问
int res = 0;
for(int i = 0; i < n; i++) {
f[i] = 1;
for(int j = 0; j < i; j++) {
if(h[i] <= h[j]) {
f[i] = max(f[i], f[j] + 1);
}
}
res = max(res, f[i]);
}
cout << res << endl;
// 第二问
int cnt = 0;
for(int i = 0; i < n; i++) {
int k = 0;
// 找到最小的那个g[k] >= h[i]
while(k < cnt && g[k] < h[i]) k++;
g[k] = h[i];
if(k >= cnt) cnt++;
}
cout << cnt << endl;
return 0;
}
复杂度分析
时间复杂度为 O ( N 2 ) O(N^2) O(N2)
对于第二问,找所有大于等于g[k]
中,最小的那个,可以使用二分查找来实现,将第二问的时间复杂度降到
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)
导弹防御系统
题目描述
为了对抗附近恶意国家的威胁,R 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如,一套系统先后拦截了高度为 3 和高度为 4 的两发导弹,那么接下来该系统就只能拦截高度大于 4 的导弹。
给定即将袭来的一系列导弹的高度,请你求出至少需要多少套防御系统,就可以将它们全部击落。
输入格式
输入包含多组测试用例。
对于每个测试用例,第一行包含整数 n,表示来袭导弹数量。
第二行包含 n 个不同的整数,表示每个导弹的高度。
当输入测试用例 n=0 时,表示输入终止,且该用例无需处理。
输出格式
对于每个测试用例,输出一个占据一行的整数,表示所需的防御系统数量。
问题分析
本质上是求最少能覆盖整个序列的上升子序列 or 下降子序列个数【可以同时用上升序列和下降序列】。
对于这道题,没有很好的解法,只能通过暴力搜索,即考虑每个数是放在上升子序列或者下降子序列中,然后搜索全局最小值。
搜索过程中,可以判断当前子序列的个数是否超过了当前的最优解,若超过则进行剪枝操作,减小搜索空间。文章来源:https://www.toymoban.com/news/detail-769231.html
这里搜索使用 DFS 实现。文章来源地址https://www.toymoban.com/news/detail-769231.html
程序代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
int n;
int q[N];
int up[N], down[N]; // 分别记录上升子序列和下降子序列
int ans; // 全局最小值
// u:数的下标
// su:上升子序列个数
// sd:下降子序列个数
void dfs(int u, int su, int sd)
{
// 剪枝
if(su + sd >= ans) return;
// su + sd < ans
if(u == n) {
ans = su + sd;
return ;
}
// 情况1:将当前数放入上升子序列
int k = 0;
while(k < su && up[k] >= q[u]) k++;
// 记录,方便恢复现场
int t = up[k];
up[k] = q[u];
if( k >= su) {
dfs(u + 1, su + 1, sd);
}
else {
dfs(u + 1, su, sd);
}
// 恢复现场
up[k] = t;
// 情况2:将当前数放入下降子序列
k = 0;
while(k < sd && down[k] <= q[u]) k++;
t = down[k];
down[k] = q[u];
if(k >= sd) {
dfs(u + 1, su, sd + 1);
}
else {
dfs(u + 1, su, sd);
}
// 恢复现场
down[k] = t;
}
int main()
{
while(cin >> n, n) {
for(int i = 0; i < n; i++) {
cin >> q[i];
}
ans = n;
dfs(0, 0, 0);
cout << ans << endl;
}
return 0;
}
到了这里,关于动态规划系列 | 最长上升子序列模型(下)| 拦截导弹一网打尽!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!