题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 60;
int n;
int h[N],up[N],down[N];
bool dfs(int depth, int u , int su ,int sd)
{
    if(su + sd > depth ) return false;
    if( u == n) return true;


    bool fg = false;
    for(int i = 1; i <= su ; i ++ )
     if(h[u] > up[i])
     {
         int t = up[i];
         up[i] = h[u];
         if(dfs(depth,u+1,su,sd)) return true;
         up[i] = t;
         fg = true;
         break;
     }
    if(!fg)
    {
        up[su + 1] = h[u];
        if(dfs(depth,u + 1,su + 1, sd )) return true;
    }
    fg = false;
    for(int i = 1 ; i <= sd ; i ++ )
    if(down[i] > h[u])
    {
        int t = down[i];
        down[i] = h[u];
        if(dfs(depth , u + 1, su ,sd )) return true;
        fg = true;
        down[i] = t;
        break;
    }
    if(!fg)
    {
        down[sd + 1] = h[u];
        if(dfs(depth, u + 1 , su , sd + 1)) return true;
    }
    return false;
}
int main()
{
    while(cin >> n, n)
    {
        for(int i = 0; i < n ; i ++ ) cin >> h[i];
        int depth = 0;
        while(!dfs(depth,0,0,0)) depth++;

        cout <<  depth << endl;
    }
}