#include #include #include #include using namespace std; typedef long long LL; const int MAXN = 1e6 + 10; const int INF = 0x3f; int n; int h[MAXN]; int up[MAXN], down[MAXN]; int ans; void dfs(int step,int l,int r){ if(l + r >= ans)return ;//如果已经比最小答案大，剪枝 if(step == n){//遍历到结束 ans = l + r;//保存答案 return ; } int pla = 0; while(pla < l && up[pla] >= h[step]){ pla++; }//求需要防最高高度 int now = up[pla]; up[pla] = h[step]; if(pla < l)dfs(step + 1, l, r); else dfs(step + 1, l + 1, r); up[pla] = now; pla = 0; while(pla < r && down[pla] <= h[step]){ pla++; }//求需要防最低高度 now = down[pla]; down[pla] = h[step]; if(pla < r)dfs(step + 1, l, r); else dfs(step + 1, l, r + 1); down[pla] = now; } int main() { while(cin >> n){ if(n == 0)break; for(int i = 0;i < n; i++){ cin >> h[i]; } ans = n; dfs(0, 0, 0);//找答案 cout << ans << endl; } return 0; }

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 10;
const int INF = 0x3f;
int n;
int h[MAXN];
int up[MAXN], down[MAXN];
int ans;
void dfs(int step,int l,int r){
	if(l + r >= ans)return ;//如果已经比最小答案大，剪枝
	if(step == n){//遍历到结束
		ans = l + r;//保存答案
		return ;
	}
	int pla = 0;
	while(pla < l && up[pla] >= h[step]){
		pla++;
	}//求需要防最高高度
	int now = up[pla];
	up[pla] = h[step];
	if(pla < l)dfs(step + 1, l, r);
	else dfs(step + 1, l + 1, r);
	up[pla] = now;
	pla = 0;
	while(pla < r && down[pla] <= h[step]){
		pla++;
	}//求需要防最低高度
	now = down[pla];
	down[pla] = h[step];
	if(pla < r)dfs(step + 1, l, r);
	else dfs(step + 1, l, r + 1);
	down[pla] = now;
}
int main()
{
	while(cin >> n){
		if(n == 0)break;
		for(int i = 0;i < n; i++){
			cin >> h[i];
		}
		ans = n;
		dfs(0, 0, 0);//找答案
		cout << ans << endl;
	}
    return 0;
}

C++ :

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;
int n;
int h[N];
int up[N];
int down[N];

bool dfs(int depth, int u, int su, int sd)
{
    if(su + sd > depth) return false;
    if(u == n) return true;
    //枚举属于哪个上升子序列
    bool flag = false;
    for(int i = 1; i <= su; i++)
    {
        if(up[i] < h[u])
        {
            int t = up[i];
            up[i] = h[u];
            if(dfs(depth, u + 1, su, sd)) return true;
            up[i] = t;
            flag = true;
            break;
        }
    }
    
    if(!flag) 
    {
        up[su + 1] = h[u];
        if(dfs(depth, u + 1, su + 1, sd)) return true;
    }
    
    flag = 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;
            down[i] = t;
            
            flag = true;
            break;
        }
    }
    
    if(!flag)
    {
        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;
    }
    
    return 0;
}