导弹防御系统 「LIS + DFS」

导弹防御系统

题目描述：

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 33 和高度为 44 的两发导弹，那么接下来该系统就只能拦截高度大于 44 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

思路：

因为不知道每个导弹到底是属于第一种导弹还是第二种导弹，所以需要进行枚举，可以用dfs来写，结合贪心 + 二分

dfs有三个参数，dfs(u, a, b),表示当时是第u个数，用了a个上升导弹，b个下降导弹

如果a + b >= ans,就表明不会产生更优的答案，可以返回，这是一个很重要的剪枝

对于当前这个点，我们先将其放在上升导弹里面，去贪心选第一个大于tr[u]的点，把他更新成tr[u]，因为上升导弹序列存的是从大到小的数，所以二分的时候要加一个参数greater()，注意如果没有符合的导弹，就说明需要一个新的上升导弹，更新一下a的参数,其他的细节自己看吧，下降导弹也是类似的道理

#include 
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)typedef long long ll;
typedef pair <int,int> pii;#define MAX 300000 + 50
int n, m, k;
int tr[MAX];
int up[105];
int down[105];
int ans;void dfs(int u, int a, int b){if(a + b >= ans)return;if(u == n + 1){ans = a + b;return;}// 放到上升序列if(tr[u] < up[a] || a == 0){up[a + 1] = tr[u];dfs(u + 1, a + 1, b);up[a + 1] = 0;}else {int p = (int)(lower_bound(up + 1, up + a + 1, tr[u], greater<int>()) - up);int x = up[p];up[p] = tr[u];dfs(u + 1, a, b);up[p] = x;}//放到下降序列if(tr[u] > down[b] || b == 0){down[b + 1] = tr[u];dfs(u + 1, a, b + 1);down[b + 1] = 0;}else{int p = (int)(lower_bound(down + 1, down + b + 1, tr[u])-down);int x = down[p];down[p] = tr[u];dfs(u + 1, a, b);down[p] = x;}
}void work(){while(cin >> n && n){mem(up, 0);mem(down, 0);for(int i = 1; i <= n; ++i)cin >> tr[i];ans = n;dfs(1, 0, 0);cout << ans << endl;}}int main(){io;work();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！