187. 导弹防御系统

187. 导弹防御系统

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

/* 
最少的最长上升子序列个数 + 最少的最长下降子序列个数 

求解：枚举(0,n - 1):dfs(u,su,sd)

*/
const int N = 60;

int n;
int a[N];
int up[N],down[N];
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 ++;
    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 ++;
    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){
        mm(a,0);
        for(int i = 0; i < n; i ++ ) cin >> a[i];
        ans = n;
        dfs(0,0,0);
        cout<<ans<<endl;        
    }        
    return 0;
}