导弹拦截

洛谷-P1020-导弹拦截

分析

题目的第二问求的是序列的不上升子序列的最小覆盖，根据Dilworth定理，它等于序列的上升子序列的最大长度。

简单的证明：

从头到尾遍历序列，打下第一个能打下的导弹，其后的导弹能打就打，在每次遍历中被打下的导弹标记为同一组。

全部的导弹被打下后，我们得到了k组不上升子序列。

子序列i + 1中每一个导弹的高度都要比子序列i的最后一个导弹的高度大，否则它会在第i次遍历中被打下。

取出全部子序列的最后一个导弹，组成一个新的长度为k的序列，这个序列是上升的。

设原序列的上升子序列的最大长度为p，显然$k\le p$，又因为最长上升子序列的任意两个元素不在同一组中（即分别属于p个组），所以$p\le k$。k = p得证。

实现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010, M = 50010;
int n, a[N];
int m, c[M];
// 在第一问中，f[i] 记录以高度为 i 的导弹为开头的不上升子序列的最大长度
// 在第二问中，f[i] 记录以高度为 i 的导弹为结尾的上升子序列的最大长度

int lowbit (int x) {
    return x & -x;
}
void modify (int idx, int val) { // f[idx] = max(f[idx], val)
    while (idx <= m) {
        c[idx] = max(c[idx], val);
        idx += lowbit(idx);
    }
}
int query (int idx) { // max(f[1],f[2],...f[idx])
    int res = 0;
    while (idx >= 1) {
        res = max(res, c[idx]);
        idx -= lowbit(idx);
    }
    return res;
}

int main () {
    while (cin >> a[n + 1]) ++ n;

    for (int i = 1; i <= n; ++ i) m = max(m, a[i]);
    // 第一问
    int res = 0;
    for (int i = n; i >= 1; -- i) {
        int val = query(a[i]) + 1;
        modify(a[i], val);
        res = max(res, val);
    }
    cout << res << endl;
    // 第二问
    memset(c, 0, sizeof(c));
    res = 0;
    for (int i = 1; i <= n; ++ i) {
        int val = query(a[i] - 1) + 1;
        modify(a[i], val);
        res = max(res, val);
    }
    cout << res << endl;
    return 0;
}