DFS - 全局最小值

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

using namespace std;

const int N = 55;

int up[N], down[N], w[N], n, res;

/*
    dfs：全局最小值

    up[]：上升系统序列，单调下降
    down[]：下降系统序列，单调上升
*/

// 当前导弹编号 上升系统个数 下降系统个数
void dfs(int u, int su, int sd){
    // 当前情况不可能使得答案变小，直接剪枝！
    if(su + sd >= res) return;
    if(u == n){
        res = su + sd;
        return;
    }

    // 情况一：当前导弹被上升系统拦截，找已有序列结尾小于自己且离自己最近的序列！
    int k = 0;
    while(k < su && up[k] >= w[u]) k ++;
    int t = up[k]; up[k] = w[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] <= w[u]) k ++;
    t = down[k]; down[k] = w[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 = 0; i < n; i ++) cin >> w[i];
        res = n;
        dfs(0, 0, 0);
        cout << res << endl;
    }
    return 0;
}

DFS - 迭代加深

所谓迭代加深：就是控制他的深度（最终答案的解），无法符合条件再进行一步步增大或减小！

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

using namespace std;

const int N = 55;

int up[N], down[N], w[N], n, res;

/*
    dfs：迭代加深

    up[]：上升系统序列，单调下降
    down[]：下降系统序列，单调上升
*/

// 当前深度（其实就是系统总数） 当前导弹编号 上升系统个数 下降系统个数
bool dfs(int depth, int u, int su, int sd){
    // 当前情况超过系统总数上限，直接回溯
    if(su + sd > depth) return false;
    if(u == n) return true;

    // 情况一：当前导弹被上升系统拦截，找已有序列结尾小于自己且离自己最近的序列！
    int k = 0;
    while(k < su && up[k] >= w[u]) k ++;
    int t = up[k]; up[k] = w[u];
    if(k < su) {
        if(dfs(depth, u + 1, su, sd)) return true;
    }
    else {
        if(dfs(depth, u + 1, su + 1, sd)) return true;
    }
    up[k] = t;

    // 情况二：当前导弹被下降系统拦截，找已有序列结尾大于自己且离自己最近的序列！
    k = 0;
    while(k < sd && down[k] <= w[u]) k ++;
    t = down[k]; down[k] = w[u];
    if(k < sd) {
        if(dfs(depth, u + 1, su, sd)) return true;
    }
    else {
        if(dfs(depth, u + 1, su, sd + 1)) return true;
    }
    down[k] = t;

    // 否则当前depth无法覆盖完全
    return false;
}

int main(){
    while(cin >> n, n){
        for(int i = 0; i < n; i ++) cin >> w[i];
        // 所谓迭代加深就是：如果当前深度depth（系统总个数）无法覆盖整个序列，则一步步增多系统个数
        int depth = 0;
        while(!dfs(depth, 0, 0, 0)) depth ++;
        // 直到可以覆盖，返回depth即系统总个数，则一定是最优解
        cout << depth <<endl;
    }
    return 0;
}