P1020题解

· · 题解

题意

给定 n 颗依次飞来的导弹的高度，现在有一个拦截系统，它的特点是：第一次拦截的导弹可以任意高度，但以后任何一次都不能高于上一次。现在要求这套系统最多能拦截多少颗导弹，以及要拦截所有导弹最少需要多少套这样的系统。

分析

题目要求两个不同的问题的答案，我们可以分开处理。

根据题意可知，由于这套系统后一次的高度不能高于前一次的高度，因此它拦截下来的导弹的高度一定是不上升的。而为了要拦截更多的导弹，我们要使得这个序列尽可能的长。于是问题便转化为求最长不上升子序列。

那么这一问就十分简单了。我们回顾一下如何实现 dp。设 d_i 表示前 i 个数中最长不上升子序列的长度，则能得到如下转移：

d_i= \max_{j<i,a_j<a_i} d_j+1

这样的转移时间复杂度为 O(n^2)，很显然，这么做在本题中 n \le 10^5 会超时。那么很容易想到使用单调栈优化。即维护一个单调不升数组，每次要加入一个数 a_i 时判断是否比栈顶大，如果是则直接加入，否则二分查找第一个小于它的位置，替换掉那个位置上的数（因为前面的数越大，后面就可能可以加更多的数）。注意，尽管这种方法能求出正确的长度，但单调栈里的序列可能不是正确的最长不上升子序列。

此部分核心代码见下：

d[1]=a[1];
for(int i=2;i<=n;i++)
{
    if(a[i]<=d[len]) d[++len]=a[i];
    else d[upper_bound(d+1,d+len+1,a[i],greater<int>())-d]=a[i];
}

时间复杂度 O(n \log n)。

既然要最少的系统，我们对于每一套系统都要“用干净”，即尽量多次使用，避免浪费。很容易想到用贪心了。每一次从已有的系统里找第一个大于等于当前高度 a_i 的系统（一定要用符合条件且最小的，大的要尽量留着给后面用），并更新当前系统的高度。若找不到这样的系统，则需要一个新的系统，并且高度为 a_i。不难发现，存储系统高度的数组也是单调不下降的，因此也可以使用二分优化查询过程。

时间复杂度 O(n \log n)，代码见下：

for(int i=1;i<=n;i++)//xl 为目前已有系统的数量，x[i] 表示第 i 个系统的高度
{
    if(x[xl]<a[i])
    {
        xl++;
        x[xl]=a[i];
    }
    else
    {
        int k=lower_bound(x+1,x+xl+1,a[i])-x;
        x[k]=a[i];
    }
}
cout<<xl;

代码

分析完毕，想必这题已经基本上解决了。这里把完整代码放出来，方便大家调试。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,ma,d[100001],a[100001],k,x[100001],xl=1,t,len=1;
int main()
{
    ios::sync_with_stdio(false);
    x[1]=0x7fffffff;
    while(cin>>a[++n]);
    d[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]<=d[len]) d[++len]=a[i];
        else d[upper_bound(d+1,d+len+1,a[i],greater<int>())-d]=a[i];
    }
    cout<<len-1<<endl;
    for(int i=1;i<=n;i++)
    {
        t=0;
        if(x[xl]<a[i])
        {
            xl++;
            x[xl]=a[i];
        }
        else
        {
            int k=lower_bound(x+1,x+xl+1,a[i])-x;
            x[k]=a[i];
        }
    }
    cout<<xl;
    return 0;
}