含分析复杂度为什么不会跑炸

题目描述

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。

第二行包含 n 个不同的整数，表示每个导弹的高度。

当输入测试用例 n=0 时，表示输入终止，且该用例无需处理。

输出格式

对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。

数据范围

1≤n≤50

输入样例

5
3 5 2 4 1
0 

输出样例

2

样例解释

对于给出样例，最少需要两套防御系统。

一套击落高度为 3,4 的导弹，另一套击落高度为 5,2,1 的导弹。

算法 : dfs

时间复杂度 $O(n * 2^n)$

首先，设置两个集合，集合 A 放置所有上升子序列，集合 B 放置所有下降子序列。

可以有一个大胆的想法，每一枚子弹要么放在集合A，要么B，换句话说，每枚子弹只有两种可能，当选择好阵营后，根据本篇博客的上一题可以在O（n）复杂度下贪心找到最优放置的位置（甚至可以用二分优化成 logn ），整套下来 n * 2 ^ n 可以解决。

看一眼数据范围，n 小于等于 50，乍以为会跑炸，但其实不会。
显然不能用二进制枚举去遍历每一种方案，但是可以从小到大枚举最少子序列数目。
假如最终答案为 ans，那么显然在 dfs 中复杂度为 ans * (2 ^ ans)。
下面证明 ans <= n / 2 上取整。

复杂度分析

假如数据很极端：
① 导弹高度从大到小或者从小到大

这种在二进制枚举确实很死亡，但是会在上诉解法中 ans == 1的时候就跑出来了，不会跑炸。

② 相同的高度很多，比如 1 1 1 1 1 1 1 1 1 0

这种如果真的连续几十个 1 确实会把dfs跑炸，但是题目输入明确表示不会有相同的高度：“ 第二行包含 n 个不同的整数，表示每个导弹的高度。 ”

③ 上升下降交叉着来，尽量不让连成较长的子序列

即便数据很诡异，像 60 70 50 65 58 这样尽量不让连成长一点的子序列，但是最差也能互相两两配对，换句话说，ans 最多也只需要 n / 2上取整。那么显然 2 ^ 25 在 3 s内是可以跑完的，或者讲究的话把 O（n）部分优化成 logn 也可以，但是这道题ans 应该很难接近 n / 2。

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 60;
const int INF = 0x3f3f3f3f;

int n;
//up表示上升子序列集合，down表示下降子序列集合
int nums[N], up[N], down[N];  

//sum-总的序列数  idx-当前安排到nums里的第几颗导弹
//u-up里面现在有几个子序列
//d-down里面现在有几个子序列
bool dfs(int sum, int idx, int u, int d) {
    if (u + d > sum) return false;  //不合法
    if (idx > n) return true;  //找到解了
    //将当前导弹放入上升子序列集里
    bool flag = true;  //判断是不是现有的容纳不下nums[idx]
    for (int i = 1; i <= u; ++ i) {
        if (up[i] < nums[idx]) { 
            int temp = up[i];  //储存，方便恢复现场
            up[i] = nums[idx]; //将当前导弹加入到该上升子序列后面
            flag = false;  //表示不需要新开一个子序列
            if(dfs(sum, idx + 1, u, d)) return true;  //递归查询该方案是否可行
            up[i] = temp; //不可行则恢复现场，尝试其他可能
            break;
        }
    }
    //在up里面新开一个子序列
    if (flag) {
        up[u + 1] = nums[idx];
        if(dfs(sum, idx + 1, u + 1, d)) return true;
        //这里不需要重置数据，因为回归当层递归时，u还是u，不是u+1
    }
    //将当前导弹放入下降子序列集里
    flag = true;
    for (int i = 1; i <= d; ++ i) {
        if (down[i] > nums[idx]) {
            int temp = down[i];
            down[i] = nums[idx];
            flag = false;
            if (dfs(sum, idx + 1, u, d)) return true;
            down[i] = temp;
            break;
        }
    }
    if (flag) {
        down[d + 1] = nums[idx];
        return dfs(sum, idx + 1, u, d + 1);
    }
    return false;
}

int main() {
    while (cin >> n, n) {
        for (int i = 1; i <= n; ++ i) cin >> nums[i];
        int ans = 1;  //从小到大枚举最小所需子序列数
        while (!dfs(ans, 1, 0, 0)) ++ ans;
        cout << ans << endl;
    }
    return 0;
}