$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. 本题就是问最少需要多少个最长上升子序列和最长下降子序列
2. up 数组存所有上升子序列的结尾数，down 数组存所有下降子序列的结尾数，ans 全局变量存最少子序列的个数
3. 直接用 dfs 暴搜枚举当前数放在上升子序列或下降子序列

可参考： 拦截导弹

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 55;

int n;
int a[N];
int up[N],down[N]; // up 存所有上升子序列的结尾，down 存所有下降子序列的结尾
int ans;

void dfs(int u,int su,int sd)
{
    if(su+sd>=ans) return; //已无法得到更好的最优解

    //所有数都已放完
    if(u==n)
    {
        ans=su+sd;
        return;
    }

    //将当前数放入上升子序列
    int k=0;
    while(k<su&&up[k]>=a[u]) k++; // up 本身随下标非严格单调递减
    int t=up[k];
    up[k]=a[u];
    if(k<su) dfs(u+1,su,sd); //不用开新组
    else dfs(u+1,su+1,sd); //需要开新组
    up[k]=t; //恢复现场

    //将当前数放入下降子序列
    k=0;
    while(k<sd&&down[k]<=a[u]) k++; // down 本身随下标非严格单调递增
    t=down[k];
    down[k]=a[u];
    if(k<sd) dfs(u+1,su,sd); //不用开新组
    else dfs(u+1,su,sd+1); //需要开新组
    down[k]=t; //恢复现场
}

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;
}