导弹防御系统--距离***搜索还有9题

闲谈:搜索是个神奇的东西,我也不知道为什么2^50能过.可能只是因为最坏是2^50左右吧QAQ.
这题思路是很简单的,对于每个点,我们有两个选择.一是放到上升序列中去,二是放到下降序列中去,假如都不能放,那么就要自己重新开一个.然后直接搜索递归即可.基于最优解肯定是要放到最近的序列连续.然后第一次找到了位子就是最优的了.
下面是代码:

#include <bits/stdc++.h>
using namespace std;
const int N=55;
int a[N],n,up[N],down[N];
bool dfs(int dep,int u,int xu,int xd)//最多开dep个序列,现在覆盖到了第几个,我的上升序列有了多少个,我的下降序列有多少个.
{
    if(xu+xd>dep) return false;
    if(u==n)      return true;
    bool flag=false;
    //枚举上升
    for(int i=1;i<=xu;i++)
    {
        if(a[u]>up[i])
        {
            int t=up[i];
            up[i]=a[u];
            flag=true;
            if(dfs(dep,u+1,xu,xd)) return true;
            up[i]=t;
            break;
        }
    }
    //假如不可以连续,创立新的
    if(!flag)
    {
        up[xu+1]=a[u];
        if(dfs(dep,u+1,xu+1,xd)) return true;
    }
    flag=false;
    //枚举下降
    for(int i=1;i<=xd;i++)
    {
        if(a[u]<down[i])
        {
            int t=down[i];
            down[i]=a[u];
            flag=true;
            if(dfs(dep,u+1,xu,xd)) return true;
            down[i]=t;
            break;
        }
    }
    //假如不可以连续,创立新的
    if(!flag)
    {
        down[xd+1]=a[u];
        if(dfs(dep,u+1,xu,xd+1)) return true;
    }
    //假如都不可以肯定return false呗.
    return false;
}

int main()
{
    while(cin>>n,n)
    {
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        int depth=1;
        while(!dfs(depth,0,0,0)) depth++;
        cout<<depth<<endl;
    }
    return 0;
}