P1020 导弹拦截

原题链接：P1020 [NOIP1999 提高组] 导弹拦截 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
相当好的一道题，用于理解使用 [[狄尔沃斯定理（Dilworth 定理）]]
当然这个定理肯定不止这么简单。

第一问就是让求一个最大不上升子序列，如果用 DP 求解，将是 \(O(n^2)\) 的时间复杂度，而这道题数据范围极限为 \(10^5\)，因此必须优化。

如果先放下优化想第二问的话，如果可以很快就可以想出来一种贪心。即维护一个序列，序列上每个值代表一个系统拦截到的最后一个导弹的高度 \(k_i\)，每加入一个导弹（高度记为 \(h\)），就在序列中找到那个高度大于等于 \(h\) 的最小的 \(k_i\)，如果没有这样的 \(k_i\) 就新加入一个系统 \(k_j\)，高度即为 \(h\)。
为什么是最小？因为总有一个 \(k_i\) 会变成 \(h\)，如果是最小的我们就可以尽量保持别的 \(k_i\) 尽可能的高，从而尽量拦截更多导弹，减少系统的使用个数。

上面说的这部分我们可以二分，维护一个单调不升的序列，这样如果没有符合的 \(k_i\)，直接在序列末端加上即可。当然维护成单调不减也行见仁见智，但加入 \(k_j\) 的方式不同。而这个单调的序列可以用单调栈来维护。

这是贪心，可以证明，如果有非贪心方案的最优方案，一定可以通过导弹的调换，变成贪心方案。

我们第二位求的，实际上就是不升子序列最小划分，根据狄尔沃斯定理（Dilworth 定理），它的数目就等于求最长上升子序列的元素数量。而我们第一问求的是最长不升子数列，根据这个定理就相当于求上升子序列的最小划分。也就是说第一二问在这种意义上，解法是一样的。

这题在 Acwing 上是一个 Dp 题，但第二问也是这样做的，差别在于数据范围，Acwing 的容许 \(O(n^2)\) 的第一问做法。

而关于实际操作就看代码吧。

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

using namespace std;

const int N = 100010;

int n, m;
int g[N], cnt[N];
int q[N], tt; // 相当一个栈

int main()
{
    while (scanf("%d", &g[ ++ n]) == 1);
    n -- ;
    
    memset(q, 0x3f, sizeof q); // 防止意外的入栈
    tt = 0; // 相当于栈的指针 
    for (int i = 1; i <= n; i ++ ) 
    {
        int l = 1, r = tt;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] < g[i]) r = mid;
            else l = mid + 1;
        }
        
        // 如果说我二分不出来符合条件的，就只能新加一个了
        if (q[l] >= g[i]) q[ ++ tt] = g[i]; 
        else q[l] = g[i];
    }
    
    cout << tt << endl;
    
    memset(q, sizeof 0, sizeof q);
    tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int l = 1, r = tt;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= g[i]) r = mid;
            else l = mid + 1;
        }
        if (q[l] < g[i] || tt == 0) q[ ++ tt] = g[i]; 
        else q[l] = g[i];
    }
    
    cout << tt << endl;
    
    return 0;
    
}