1、拦截导弹
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。
某天,雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,导弹数不超过1000),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
共一行,输入导弹依次飞来的高度。
输出格式
第一行包含一个整数,表示最多能拦截的导弹数。
第二行包含一个整数,表示要拦截所有导弹最少要配备的系统数。
数据范围
雷达给出的高度数据是不大于 30000的正整数,导弹数不超过 1000。
输入样例:
389 207 155 300 299 170 158 65
输出样例:
6
2
思路:
基本思路:
每次都拦截最长下降子序列
求的是第一次最多拦截的导弹数
还有最少需要配备多少个系统才能拦截所有导弹
先求最长不上升子序列,然后再求最多需要多少个系统才能完全拦截所有导弹
1、对于最长不上升子序列:动态规划求一遍最长上升子序列即可
2、对于需要的导弹拦截系统数:开一个数组,每个位置记录每个系统拦截结尾的导弹的高度,每次用二分搜索:
(1)找到这个数组中第一个大于等于(lower_bound)当前处理的导弹的高度,然后把这个序列的结尾改为当前导弹(即修改数组的值)
(2)如果找不到,那就另外开一个序列(数组大小+1)
另:
若数组升序排列
lower_bound(begin, end, a) 返回数组[begin, end)之间第一个大于或等于a的地址,找不到返回end
upper_bound(begin, end, a) 返回数组[begin, end)之间第一个大于a的地
址,找不到返回end
若数组降序排列,可写上比较函数greater<>()
lower_bound(begin, end, a, greater<>()) 返回数组[begin, end)之间第一个小于或等于a的地址,找不到返回end
upper_bound(begin, end, a, greater<>()) 返回数组[begin, end)之间第一个小于a的地址,找不到返回end
非数值数组的情况可选择手写比较函数,如
bool cmp(node a, node b)
{
if(a.value1 != b.value1) return a.value1 < b.value1;
else return a.value2 < b.value2;
}
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n, a[maxn];
int f[maxn], g[maxn];
//每次都拦截最长下降子序列
//如果拦截完还有,就要把拦截过的去掉
//求的是第一次最多拦截的导弹数
//还有最少需要配备多少个系统才能拦截所有导弹
// 题目的第二问,对于第i号导弹,要么选择末尾导弹高度最小的拦截系统,要么新创一个拦截系统,用一个数字即每套拦截系统此时所拦截的最后一个导弹高度,来表示该系统。
// 这样就得到了一个数组,数组最终长度就是所需最少拦截系统数目。
int main()
{
while(cin >> a[n]) n ++;
int ans = 0, cnt = 0;
for(int i = 0; i < n; i ++)
{
f[i] = 1;
for(int j = 0; j < i; j ++)
{
if(a[i] <= a[j]) f[i] = max(f[i], f[j] + 1);
}
ans = max(ans, f[i]);
//数组g的每个元素代表一套导弹拦截系统的拦截序列
//g[i]表示此时第i套导弹拦截系统所拦截的最后一个导弹的高度
int p = lower_bound(g, g+cnt, a[i]) - g;
if(p == cnt) g[cnt ++] = a[i]; //a[i]开创一套新拦截系统
else g[p] = a[i]; //a[i]成为第p套拦截系统最后一个导弹高度
}
cout << ans << endl;
cout << cnt << endl;
return 0;
}
2、导弹防御系统(DFS+DP)
为了对抗附近恶意国家的威胁,R 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如,一套系统先后拦截了高度为 3和高度为 4的两发导弹,那么接下来该系统就只能拦截高度大于 4的导弹。
给定即将袭来的一系列导弹的高度,请你求出至少需要多少套防御系统,就可以将它们全部击落。
输入格式
输入包含多组测试用例。
对于每个测试用例,第一行包含整数 n,表示来袭导弹数量。
第二行包含 n
个不同的整数,表示每个导弹的高度。
当输入测试用例 n=0 时,表示输入终止,且该用例无需处理。
输出格式
对于每个测试用例,输出一个占据一行的整数,表示所需的防御系统数量。
数据范围
1≤n≤50
输入样例:
5
3 5 2 4 1
0
输出样例:
2
样例解释
对于给出样例,最少需要两套防御系统。
一套击落高度为 3,4
的导弹,另一套击落高度为 5,2,1
的导弹。
思路:
本题不能像上题一样可以简单的划分状态(贪心),只能爆搜(因为没有固定规律,状态太难定义)
DFS求最小数目:
up表示上升子序列的结尾,down表示下降子序列的结尾
代码:
#include<iostream>
using namespace std;
const int N = 55;
int a[N], ans, up[N], down[N], n;
void dfs(int u, int d, int t) //u表示上升的系统个数,d表示下降的系统个数,t表示第t个数
{
if(u + d >= ans) return ;
if(t == n){
if(u + d < ans)ans = u + d;
return ;
}
int i;
for(i = 1; i <= u; i++) //找到第一个末尾数小于a[t]的导弹系统
if(up[i] < a[t])break;
int temp = up[i];
up[i] = a[t];//添加到该导弹系统中
dfs(max(u, i), d, t + 1);
up[i] = temp; //恢复现场
for(i = 1; i <= d; i++)//找到第一个末尾数大于a[t]的导弹系统
if(down[i] > a[t])break;
temp = down[i];
down[i] = a[t];//添加到该导弹系统中去
dfs(u, max(d, i), t + 1);
down[i] = temp;//恢复现场
}
int main()
{
while(scanf("%d", &n) != EOF && n != 0){
ans = 100;
for(int i = 0; i < n; i++)
cin >> a[i];
dfs(0, 0, 0);
printf("%d\n", ans);
}
return 0;
}
3、最长公共上升子序列
一个数的序列 bi,当 b1<b2<…<bS的时候,我们称这个序列是上升的。
对于给定的一个序列(a1,a2,…,aN),我们可以得到一些上升的子序列(ai1,ai2,…,aiK),这里1≤i1<i2<<iK≤N。
比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等等。
这些子序列中和最大为18,为子序列(1,3,5,9)的和。
你的任务,就是对于给定的序列,求出最大上升子序列和。
注意,最长的上升子序列的和不一定是最大的,比如序列(100,1,2,3)的最大上升子序列和为100,而最长上升子序列为(1,2,3)。
输入格式
输入的第一行是序列的长度N。
第二行给出序列中的N个整数,这些整数的取值范围都在0到10000(可能重复)。
输出格式
输出一个整数,表示最大上升子序列和。
数据范围
1≤N≤1000
输入样例:
7
1 7 3 5 9 4 8
输出样例:
18
思路:
结合了最长公共子序列和最长上升子序列两个问题
1、对于最长公共子序列:
状态表示:f[i][j]:表示在a[1–i],b[1–j]中,以b[j]结尾的公共子序列长度
属性:最大值
2、对于最长上升子序列:
状态表示:f[i][j]:表示在a[1–i],b[1–j]中,以b[j]结尾的最长上升子序列长度
属性:最大值
注:讨论是否包含a【i 】(两种情况)
代码:
#include <iostream>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];
int main()
{
//input
cin >> n;
for (int i = 1; i <= n; ++ i) cin >> a[i];
for (int i = 1; i <= n; ++ i) cin >> b[i];
//dp
for (int i = 1; i <= n; ++ i)
{
int maxv = 1;
for (int j = 1; j <= n; ++ j)
{
f[i][j] = f[i - 1][j];
if (b[j] == a[i]) f[i][j] = max(f[i][j], maxv);//包含a[i]
if (b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1); //不包含a[i]
}
}
//find result
int res = 0;
for (int i = 0; i <= n; ++ i) res = max(res, f[n][i]);
cout << res << endl;
return 0;
}