acwing187. 导弹防御系统

题目

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

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

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

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

IO

思路

用up[k]和down[k]记录第k套上升（下降）系统目前所拦截的最后一个导弹
dfs(u,v,t)意味着已有u个上升，v个下降，正在处理第t个数

#include<iostream>
using namespace  std;
const int N=55;
int n,a[N],up[N],down[N],ans;
void dfs(int u,int d,int cur){
    if(u+d>=ans)return ;//当前已经超过最小的ans则不需要再搜索了
    if(cur==n){
       if(u + d < ans)ans = u + d;//已经搜索了n个则更新答案
        return ;
    }
    int i;
    for(i=1;i<=u;i++)
        if(up[i]<a[cur])break//找到第一个小于当前高度的上升序列
    int temp=up[i];//保存
    up[i]=a[cur];//更新，将这个更高的高度放到up中
    dfs(max(u,i),d,cur+1);   //max看是否上升序列是否增加
    up[i]=temp;//回溯
    
    for(i=1;i<=d;i++)
        if(down[i]>a[cur])break;
    temp=down[i];
    down[i]=a[cur];
    dfs(u,max(i,d),cur+1);
    down[i]=temp;
}

int main(){
    while(cin>>n,n){
        for(int i=0;i<n;i++)cin>>a[i];
        ans=100;
        dfs(0,0,0);
        cout<<ans<<endl;
    }
    return 0;
}