站外题

#include<iostream>
#include<cstring>
using namespace std;
int n,ans;//初始ans最少需要n个序列
int a[55];
int up[55],down[55];
void dfs(int u,int su,int sd)//已经搜完了u个导弹，创建了su个上升子序列，sd个下降子序列
{
    if(su+sd>=ans)return;
    if(u==n)
    {
        ans=min(ans,su+sd);
        return;
    }
    
    //第一种情况：放到上升子序列中
    int k=1;
    while(k<=su&&up[k]>=a[u])k++;
    int temp1=up[k];//注意回溯
    up[k]=a[u];
    if(k>su)dfs(u+1,su+1,sd);
    else dfs(u+1,su,sd);
    up[k]=temp1;//回溯
    
    //第二种情况：放到下降子序列中
    k=1;
    while(k<=sd&&down[k]<=a[u])k++;
    int temp2=down[k];
    down[k]=a[u];
    if(k>sd)dfs(u+1,su,sd+1);
    else dfs(u+1,su,sd);
    down[k]=temp2;//注意：搜索这一层的东西就是这一层的，和下一层没关系，下一层的只与传的参数和全局变量有关系
}
int main()
{
    while(cin>>n&&n)
    {
 //     memset(up,0,sizeof up);
//      memset(down,0,sizeof down);
        ans=n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        dfs(0,0,0);
        cout<<ans<<endl;
    }
    return 0;
}