AcWing 187. 导弹防御系统
原题链接
中等
作者:
dellqang
,
2020-07-05 18:34:09
,
所有人可见
,
阅读 956
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 60;
int a[N];
int up[N], down[N];
int ans;
int n;
// su表示当前上升导弹的数目, 同理sd
void dfs(int t, int su, int sd){
if(su+sd >= ans) return; // 这一步剪枝,提前减掉不好的分枝 >= 相比 > 时间复杂度更低
if(t==n) {
ans = su + sd; // 由于上一步剪枝,因此ans为当前方案数的最小值
return;
}
// 将当前导弹加入上升序列中
int k = 0;
while(k<su&&a[t]<=up[k]) k++;
int status = up[k];
up[k] = a[t];
if(k>=su) dfs(t+1, su+1, sd);
else dfs(t+1, su, sd); // 当时把这一步搞丢了
up[k] = status;
// 将当前导弹加入下降序列中
k=0;
while(k<sd&&a[t]>=down[k]) k++;
status = down[k];
down[k] = a[t];
if(k>=sd) dfs(t+1,su, sd+1);
else dfs(t+1, su, sd);
down[k] = status;
}
int main(){
while(cin>>n, n){
for(int i=0; i<n; i++) cin >> a[i];
ans = n;
dfs(0,0,0);
cout << ans << endl;
}
return 0;
}