八、AcWing 187. 导弹防御系统
1.题目
本题链接：导弹防御系统
本博客提供本题截图：
2.逻辑解释
用up[k]和down[k]记录第k套上升（下降）系统目前所拦截的最后一个导弹，dfs(u,v,t)意味着已有u个上升，v个下降，正在处理第t个数，这里还涉及到一个贪心的思路：假设现在要把一个数放入一个上升序列，那么一定是所有能放入的上升序列中，最后一个元素最大的那一个.
3.AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 55; int n; int h[N], up[N], down[N]; int res; void dfs(int u, int su, int sd) { if (su + sd >= res) return; if (u == n) { res = su + sd; return; } int k = 0; while (k < su && up[k] >= h[u]) k ++; int t = up[k]; up[k] = h[u]; if (k >= su) dfs(u + 1, su + 1, sd); else dfs(u + 1, su, sd); up[k] = t; k = 0; while (k < sd && down[k] <= h[u]) k ++; t = down[k]; down[k] = h[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 >> h[i]; res = n; dfs(0, 0, 0); cout << res << endl; } return 0; }
九、AcWing 272. 最长公共上升子序列
1.题目
本题链接：最长公共上升子序列
本博客提供本题截图：
2.AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 3010; int a[N], b[N], f[N][N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i]; for (int i = 1; i <= n; i ++ ) cin >> b[i]; 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 (a[i] == b[j]) f[i][j] = max(f[i][j], maxv); if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1); } } int res = 0; for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]); cout << res << endl; return 0; }
十、额外的练习题
P1020 [NOIP1999 普及组] 导弹拦截
P1439 【模板】最长公共子序列
P1280 尼克的任务
P2758 编辑距离
P4933 大师
P1077 [NOIP2012 普及组] 摆花
P1233 木棍加工
