P1020 导弹拦截

· · 题解

显然，第一问求的是最长不上升子序列。

于是接下来直接抛开第一问不谈，也不考虑优化，直接考虑第二问。待会就知道原因了。

引理：Dilworth 定理

狄尔沃斯定理亦称偏序集分解定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目。

该定理在该问题上可以理解成：把序列分成不上升子序列的最少个数，等于序列的最长上升子序列长度。把序列分成不降子序列的最少个数，等于序列的最长下降子序列长度。

则第二问等价于最长上升子序列。

贪心

先不管引理对我们有什么用，我们直接思考第二问贪心怎么做。

对于每个数，既可以把它接到已有的导弹拦截后面，也可以建立一个新系统。要使子序列数最少，应尽量不建立新序列。

另外，应让每个导弹系统的末尾尽可能大，这样能接的数更多。因为一个数若能接到小数后面，必然能接到大数后面，反之则不成立。根据这些想法，可总结出如下贪心流程：

从前往后扫描每个数，对于当前数

  1. 若现有子序列的结尾都小于它，则创建新子序列。
  2. 否则，将它放到结尾大于等于它的最小数后面。

贪心证明

我们可以知道，证明 A=B，可证 A\leq B 且 A\geq B。

记 A 为贪心解，B 为最优解。

  1. 贪心解能覆盖所有数，且形成的都是不升序列，因此合法。由定义，B≤A。

  2. 假设最优解对应的方案和贪心方案不同，从前往后找到第一个不在同一序列的数 x。假设贪心解中 x 前面的数是 a，最优解中 x 前面的数是 b，a 后面的数是 y，由于贪心会让当前数接到大于等于它的最小数后面，所以 x,y≤a≤b。
    此时，在最优解中，把 x 一直到序列末尾，和 y 一直到序列末尾交换位置，这样做不影响正确性，也不增加序列个数，但会使 x 在最优解和贪心解中所处的位置相同。由于序列中的数是有限的，只要一直做下去，一定能使最优解变为贪心解。因此 A≤B。

则 A=B，即我们的贪心解等于最优解。

放一下第二问的贪心代码：

for (int i = 1; i <= l; i++) {
    int k = 1;
    while (k <= cnt && g[k] < a[i]) k++;
    if (k > cnt) g[++cnt] = a[i];
    else g[k] = a[i];
}
cout << cnt << endl;

等等，第二问根据引理是求最长上升子序列，但是贪心也可以求。说明我们的贪心解法等于最长上升子序列 ！！（引理作用即在此处）

贪心可以求上升子序列，自然连第一问求的最长不上升子序列也可以求了，直接修改一下代码即可。

于是可以写出如下代码：

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

const int N = 1e5 + 5;
int a[N], x, l, dp[N], maxn;
int g[N], cnt;

int main() {
    while (cin >> x) a[++l] = x;
    for (int i = 1; i <= l; i++) {
        int k = 1;
        while (k <= cnt && g[k] >= a[i]) k++;
        if (k > cnt) g[++cnt] = a[i];
        else g[k] = a[i];
    }
    cout << cnt << endl;
    cnt = 0;
    for (int i = 1; i <= l; i++) {
        int k = 1;
        while (k <= cnt && g[k] < a[i]) k++;
        if (k > cnt) g[++cnt] = a[i];
        else g[k] = a[i];
    }
    cout << cnt << endl;
}

最坏复杂度 O(n^2)，但是数据很水，可以完美通过此题。

我们也可以对此代码进行二分优化（即查找 k 的时候）：

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

const int N = 2e5 + 5;
int a[N], x, n, dp[N], maxn;
int g[N], cnt;

int main() {
    while (cin >> x) a[++n] = x;
    g[0] = 2e9; 
    for (int i = 1; i <= n; i++) {
        if (a[i] <= g[cnt]) g[++cnt] = a[i];
        else {
            int l = 1, r = cnt;
            while (l < r) {
                int mid = l + r >> 1;
                if (g[mid] < a[i]) r = mid;
                else l = mid + 1;
            }
            g[l] = a[i];
        }
    }
    cout << cnt << endl;   // 最长不上升子序列
    cnt = 0;
    g[0] = -2e9;
    for (int i = 1; i <= n; i++) {
        if (a[i] > g[cnt]) g[++cnt] = a[i];
        else {
            int l = 1, r = cnt;
            while (l < r) {
                int mid = l + r >> 1;
                if (g[mid] >= a[i]) r = mid;
                else l = mid + 1;
            }
            g[l] = a[i];
        }
    }
    cout << cnt << endl;   // 最长上升子序列
}