二刷提高课，题解目录在这里— 提高课的题解目录

像这种两种策略无法使用贪心来些，并且无法用记忆化搜索来记录中间可能性
只能用爆搜，暴力枚举每个点的可能性
很明显每个点处理不了是递增还是递减所以只能暴搜
注意虽然这里明面上是2^50但是加入了减枝实际枚举的并没有那么多

#include<iostream>
using namespace std;
int a[55];
int up[55];
int down[55];
int res;
int n;
void dfs(int u,int ud,int dd)
{
    if(ud+dd>=res)return;//减枝核心
    if(u==n)res=ud+dd;
    //将其放在递增序列里
    int k=0;
    while(k<ud&&up[k]>=a[u])k++;//找到第一个小于的
    int t=up[k];
    up[k]=a[u];
    if(k<ud)dfs(u+1,ud,dd);
    else dfs(u+1,ud+1,dd);
    up[k]=t;
    //将其放在递减序列里
    k=0;
    while(k<dd&&down[k]<=a[u])k++;//找到第一个大于的
    t=down[k];
    down[k]=a[u];
    if(k<dd)dfs(u+1,ud,dd);
    else dfs(u+1,ud,dd+1);
    down[k]=t;
}
int main()
{
    while(cin>>n,n)
    {
        for(int i=0;i<n;i++)cin>>a[i];
        res=n;//最坏情况每个导弹需要一个系统
        dfs(0,0,0);//因为第一个点就要从递增递减两方面考虑所以从0开始
        cout<<res<<endl;
    }
}