题解 P1020 【导弹拦截】

· · 题解

这个题目实际上是要求求出最长不下降子序列以及多少个这样的序列可以覆盖所有的点。

第一问相对来说比较简单，我们可以从后往前求最长不下降子序列（从前往后同理，我按照从后往前写的）。

对于最长上升子序列，我解释的实在达不到OI WIKI的水平，以下来自OI WIKI:

首先，定义a_i...a_n为原始序列,d为当前的不下降子序列，len为子序列的长度，那么d_{len}就是长度为len的不下降子序列末尾元素。

初始化：d_1=a_1,len=1。

现在我们已知最长的不下降子序列长度为1，那么我们让i从2到n循环，依次求出前i个元素的最长不下降子序列的长度，循环的时候我们只需要维护好d这个数组还有len就可以了。关键在于如何维护。

考虑进来一个元素a_i：

元素大于d_{len}，直接d_{++len}=a_i即可，这个比较好理解。

元素等于d_{len}，因为前面的元素都小于它，所以这个元素可以直接抛弃。

元素小于d_{len}，找到第一个大于它的元素，插入进去，其他小于它的元素不要。

那么代码如下：

for (int i = 0; i < n; ++i) scanf("%d", a + i);
memset(dp, 0x1f, sizeof dp);
mx = dp[0];
for (int i = 0; i < n; ++i) {
  *std::lower_bound(dp, dp + n, a[i]) = a[i];
}
ans = 0;
while (dp[ans] != mx) ++ans;

（PS：像我一样的新手可能不理解lower\_bound和upper\_bound。前者返回已经排好序的序列中大于等于输入元素的第一个位置，后者返回已经排好序的序列中大于输入元素的第一个位置。这两个查找的时间复杂度均为O(logn)）

以上为OI WIKI对于最长上升子序列的详解，尽管代码有点复杂，大家也一定要好好理解（我建议手动模拟下实现的过程），因为我以下的讲解是基于这份代码做了修改，理解了这份代码能帮助大家理解以下的内容。

OI WIKI的讲解是求的最长上升子序列，然而我们希望求的是希望最长不下降序列，这样相当于等于当前最高点的情况也需要考虑进去，使len+1。

我的做法是每次加入元素求upper\_bound，对于没有重复的情况返回值与lower\_bound并没有区别，对于出现重复的情况，如果是在最后加到末尾，如果不是最后的情况我们选择将当前找到的这个大于当前数位置换成现在这个更小的数，以便于后面结果的更优（这一句结合OI WIKI的讲解理解一下）。最后我们发现这样的过程代码实现中十分容易，令当前的数覆盖所有当前找到的位置就可以了。

接下来就是稍微麻烦一点的第二问，实际上从前向后就一个最长上升子序列就可以解决，答案就是这个序列的长度，我想说说自己的想法，如果有错误请读者大佬指出。

我们考虑找出来的最长的序列，其左上和右下的点一定可以和这个求出的序列中的某个点划分为从左上到右下的一层，如此划分成的层数就是需要的系统数，我们为了保证每个点都有属于自己的一层，求出最长上升子序列就可以满足这个要求。

（PS：这个第二问和机房一个大佬讨论了两节自习没有找到特别严谨的证明，大家可以意会一下，如果有严谨的证明方法请读者大佬提出）

第二问另一种做法是贪心，因为本蒟蒻意在复习dp，没有考虑，有兴趣的同学可以翻看其他大佬的题解。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[100010],d[100010],c[100010],n=0;
int main()
{
    int x;
    while(cin>>x)
    {
        a[++n]=x;
    }
    memset(d,0x3f,sizeof(d));
    memset(c,0x3f,sizeof(c));
    int p=0;
    for(int i=n,j=1; i>=1; i--, j++)
    {
        p=upper_bound(d+1,d+1+n,a[i])-d;
        d[p]=a[i];
        p=lower_bound(c+1,c+1+n,a[j])-c;
        c[p]=a[j];
    }
    int len=1;
    while(d[len]!=d[0])
    {
        len++;
    }
    cout<<len-1<<endl;
    len=1;
    while(c[len]!=c[0])
    {
        len++;
    }
    cout<<len-1<<endl;
    return 0;
}