《算法提高课》题解与笔记上线啦！(链接就是这个){: style=”color: #FF0000”}

创建时间2024-1-23

$$ #1 187.导弹防御系统 $$

最长上升子序列模型

原题Link

Code:

# include <bits/stdc++.h>
using namespace std;

const int N = 60;

int n, ans;
int h[N], up[N], down[N];

void dfs(int u, int su, int sd){ // 拦截了多少导弹，有多少上升的拦截系统，有多少下降的拦截系统 
    if(su + sd >= ans) return;
    if(u == n + 1){
        ans = su + sd;
        return;
    }

    // 情况一：将当前数放在上升子序列中

    int k = 1;
    while(k <= su && up[k] >= h[u]) k ++;
    int t = up[k];
    up[k] = h[u];
    if(k <= su) dfs(u + 1, su, sd);
    else dfs(u + 1, su + 1, sd);
    up[k] = t;

    // 情况二：将当前数放在下降子序列中

    k = 1;
    while(k <= sd && down[k] <= h[u]) k ++;
    t = down[k];
    down[k] = h[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 = 1; i <= n; i ++)
            scanf("%d", &h[i]);

        ans = n; // 最坏情况有n个系统 
        dfs(1, 0, 0);

        printf("%d\n", ans);
    }

    return 0;
}