分析：

和上一题导弹的区别在于，上一题只能是单调下降的的序列。
而这道题可能有单调上升或者单调下降的序列。
像之前的贪心：

只是针对单调递减序列的，当一套系统可能递增可能递减的时候，就会出现四种情况，最后结果不是对应的最大上升子序列长度的值了。

没有什么好的办法，结合上题求最小系统数的解法，dfs分别求上升系统和下降系统的最小值和。

疑问：

$\cal{Question:}$
1.那么既然要求最小步数，为什么不用bfs呢？
$\cal{ANS}$： bfs可能会爆栈， 并且相比dfs，不好剪枝。

$\cal{Question:}$
2.

 if(in + dn >= res)return ;

这段代码中， > 和 >= 有什么本质的区别吗？
$\cal{ANS}$： 等待更新。

更新:
通过cout发现， 如果是> , 当 in + dn == res,依旧会继续计算，直到step == n,会造成许多不必要的计算，因此会超时 本来的复杂度，是2^n,会超时，通过剪枝减小了复杂度， 用 > 的时候，没有完全剪枝。
>的时候：

>= 的时候：

代码：

#include<iostream>
#include<cstring>
using namespace std;

const int N = 51;
int a[N], res;
int u[N], d[N], n;

/*in表示上升系统的个数，dn表示下降系统的个数, u代表当前判断到了第几个数*/
void dfs(int step, int in, int dn)
{
    /* > 和 >= 有什么本质的区别吗？*/
    if(in + dn >= res)return ;
    if(step == n)
    {
        res = in + dn;return ;
    }
    /*求上升系统的个数*/
    int k = 0;
    /*以结尾元素组成的数组u， 循环找到第一个结尾元素小于当前数的序列*/
    /*必须要加=，因为是严格单调的序列*/
    while(k < in && u[k] >= a[step])k++;
    /*对于dfs，算出一种ans之后，要重置为原来的状态重新寻找新的ans，所以在递归结束时要恢复变量*/
    int t = u[k];
    /*把当前数加到对应序列里，即更新序列中的结尾元素为a[step]*/
    u[k] = a[step];
    /*k < in 代表没有新增序列，因此in的数量不变*/
    if(k < in)dfs(step + 1, in, dn);
    else dfs(step + 1, in + 1, dn);
    /*恢复变量*/
    u[k] = t;

    /*下降系统*/
    k = 0; 
    while(k < dn && d[k] <= a[step])k++;
    t = d[k];
    d[k] = a[step];
    if(k < dn)dfs(step + 1, in, dn);
    else dfs(step + 1, in, dn + 1);
    d[k] =t;
}

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