【动态规划-最长上升子序列模型part2】：拦截导弹、导弹防御系统、最长公共上升子序列【已更新完成】

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()
{//inputcin >> n;for (int i = 1; i <= n; ++ i) cin >> a[i];for (int i = 1; i <= n; ++ i) cin >> b[i];//dpfor (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 resultint res = 0;for (int i = 0; i <= n; ++ i) res = max(res, f[n][i]);cout << res << endl;return 0;
}