187. 导弹防御系统
题意
为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。
给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。
思路
和 AcWing 1010. 拦截导弹 很类似的一题 唯一不同的是不仅可以选择上升子序列 也可以选择下降子序列
因为数据非常的小 所以我们选择爆搜 对于每一个元素 分为两种情况
一种是选择把它放到结尾元素小于当前数的最大的上升子序列中
另一种是放到结尾元素大于当前数的最小的下降子序列中
注意每次搜完之后要恢复现场
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 6000; int n; int a[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 = 1; while (k <= su && a[u] <= up[k])k++; int t = up[k]; up[k] = a[u]; if (k <= su)dfs(u + 1, su, sd); else dfs(u + 1, su + 1, sd); up[k] = t; //第二种情况 将当前数放在下降子序列后面 k = 1; while (k <= sd && a[u] >= down[k])k++; t = down[k]; down[k] = a[u]; if (k <= sd)dfs(u + 1, su, sd); else dfs(u + 1, su, sd + 1); down[k] = t; } void solve() { while (cin >> n, n) { for (int i = 0; i < n; ++i)scanf("%d", a + i); res = INF; dfs(0, 0, 0); cout << res << endl; } } int main() { //int t; cin >> t; //while (t--) solve(); return 0; }
