AcWing 187. 导弹防御系统
原题链接
中等
深搜 + 贪心 + 二分法【边界是魔鬼】
相关题目
数的范围
最长上升子序列
代码
#include<iostream>
using namespace std;
const int N = 55;
int a[N], n;
int f[N], g[N];
int res;
void dfs(int u, int s, int t) {
//剪枝
if(s + t >= res) {
return ;
}
if(u == n) {
res = min(res, s + t);
return ;
}
//1.插入到上升子序列中
//f保存了每个子序列的最后一个元素,且f递增
//插入到末尾
if(s == 0 || f[s - 1] < a[u]) {
f[s] = a[u];
dfs(u + 1, s + 1, t);
}
//将区间分为两半,左半区间值>=a[u],右半区间值 < a[u]
//找到左半区间的右边界
else{
int l = 0, r = s - 1;
while(l < r) {
int mid = l + r >> 1;
if(a[u] <= f[mid]) r = mid;
else l = mid + 1;
}
int tmp = f[l];
f[l] = a[u];
dfs(u + 1, s, t);
f[l] = tmp; //恢复现场
}
//2.插入到下降子序列中
//g保存了每个子序列的最后一个元素, 且g递减
if(t == 0 || a[u] < g[t - 1]) {
g[t] = a[u];
dfs(u + 1, s, t + 1);
}
//将右半区间定义为小于等于a[u],找到这个区间的左边界
else{
int l = 0, r = t - 1;
while(l < r) {
int mid = l + r >> 1;
if(a[u] >= g[mid]) r = mid;
else l = mid + 1;
}
int tmp = g[l];
g[l] = a[u];
dfs(u + 1, s, t);
g[l] = tmp;
}
}
int main() {
while(cin >> n, n) {
for(int i = 0; i < n; i++) cin >> a[i];
res = n;
dfs(0, 0, 0);
cout << res << endl;
}
return 0;
}