acwing算法提高之动态规划--最长上升子序列模型（下）

1 基础知识

暂无。。。

2 模板

暂无。。。

3 工程化

题目1：拦截导弹。给你N个数，第（1）问求最长下降子序列，第（2）问求需要多少个下降序列才能把所有元素覆盖住？

解题思路：第（1）直接用最长上升子序列的模型即可。第（2）问，需要贪心做法。

贪心做法的关键步骤，有

1. 遍历每一个元素x：
2. 如果现有子序列结尾值均小于等于x，新开一个下降子序列，x作为第一个元素。否则，将x插入到最不浪费空间的那个子序列结尾处（即大于等于x的最小值）。
3. 开了多少个下降子序列，就是最终答案。

通过发现可以得到，上述贪心做法，和最长上升子序列的$O(nlogn)$做法一致，虽然代表的含义是不一样的，但答案是一样的。

C++代码如下，

#include <iostream>
#include <vector>

using namespace std;

const int N = 1010;
int n;
int a[N];
int f[N];

int main() {
    while (cin >> a[n]) n++;
    
    int ans1 = 0;
    for (int i = 0; i < n; ++i) {
        f[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (a[j] >= a[i]) {//注意可以取等于号
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans1 = max(ans1, f[i]);
    }
    cout << ans1 << endl;
    
    //求需要多少个下降子序列才能够把所有元素覆盖住
    vector<int> vec;
    for (int i = 0; i < n; ++i) {
        //在vec中找到大于a[i]，且值最小的元素的下标
        int idx = -1;
        for (int j = 0; j < vec.size(); ++j) {
            if (vec[j] >= a[i]) {//注意可以取等于号
                idx = j;
                break;
            }
        }
        if (idx == -1) {//说明没有找到，vec中的元素都比a[i]要小
            vec.emplace_back(a[i]);
        } else {//说明找到了
            vec[idx] = a[i];
        }
    }
    cout << vec.size() << endl;
    
    return 0;
}

可以将第（2）问求需要多少个下降子序列才能够把元素覆盖住，转换为求最长上升子序列。C++代码如下，

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 1010;
int n;
int a[N];
int f[N];

int main() {
    while (cin >> a[n]) n++;
    
    int ans1 = 0;
    for (int i = 0; i < n; ++i) {
        f[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (a[j] >= a[i]) {//注意可以取等于号
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans1 = max(ans1, f[i]);
    }
    cout << ans1 << endl;
    
    //求需要多少个下降子序列才能够把所有元素覆盖住
    memset(f, 0, sizeof f);
    //转换成求最长上升子序列
    int ans2 = 0;
    for (int i = 0; i < n; ++i) {
        f[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans2 = max(ans2, f[i]);
    }
    cout << ans2 << endl;
    
    return 0;
}

更进一步，可以将上述求最长上升子序列的做法的时间复杂度从$O(n^2)$优化到$O(nlogn)$。C++代码如下，

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 1010;
int n;
int a[N];
int f[N];

int main() {
    while (cin >> a[n]) n++;
    
    int ans1 = 0;
    for (int i = 0; i < n; ++i) {
        f[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (a[j] >= a[i]) {//注意可以取等于号
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans1 = max(ans1, f[i]);
    }
    cout << ans1 << endl;
    
    //求需要多少个下降子序列才能够把所有元素覆盖住
    vector<int> q; //q[i]表示长度为length（length = i + 1）的上升子序列的结尾元素的最小值为q[i]
    for (int i = 0; i < n; ++i) {
        //在q中找到大于等于a[i]的第一个元素
        int idx = lower_bound(q.begin(), q.end(), a[i]) - q.begin();
        if (idx == q.size()) {//说明没有找到，q中所有的元素都小于a[i]
            q.emplace_back(a[i]);
        } else {//说明找到了
            q[idx] = a[i]; 
        }
    }
    int ans2 = q.size();
    cout << ans2 << endl;
    
    return 0;
}

题目2：导弹防御系统。

解题思路：dfs。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 55;
int a[N];
int up[N];
int down[N];
int n;
int ans;

void dfs(int u, int sup, int sdown) {
    if (sup + sdown >= ans) return;
    if (u == n) {
        ans = sup + sdown;
        return;
    }
    
    //(1)将a[u]归到上升子序列中
    int k = 0;
    while (k < sup && up[k] >= a[u]) k++;
    if (k < sup) {
        int t = up[k];
        up[k] = a[u];
        dfs(u + 1, sup, sdown);
        up[k] = t;
    } else {
        up[k] = a[u];
        dfs(u + 1, sup + 1, sdown);
    }
    
    //(2)将a[u]归到下降子序列中
    k = 0;
    while (k < sdown && down[k] <= a[u]) k++;
    if (k < sdown) {
        int t = down[k];
        down[k] = a[u];
        dfs(u + 1, sup, sdown);
        down[k] = t;
    } else {
        down[k] = a[u];
        dfs(u + 1, sup, sdown + 1);
    }
    return;
}

int main() {
    while (cin >> n, n) {
        for (int i = 0; i < n; ++i) cin >> a[i];
        
        ans = n;
        dfs(0, 0, 0);
        cout << ans << endl;
    }
    
    return 0;
}

题目3：