无限

[题解]洛谷P1020:导弹拦截
原题链接:P1020 导弹拦截本题非常经典,是LIS(最长不降子序列)问题的模板题。这一类题目虽然理解上比较简单,...
扫描右侧二维码阅读全文
12
2019/06

[题解]洛谷P1020:导弹拦截

原题链接:P1020 导弹拦截


本题非常经典,是LIS(最长不降子序列)问题的模板题。
这一类题目虽然理解上比较简单,但问题形式多样,审题时需认真并结合一定的数学推导。

本题有两种思路,由于思路的不同导致时间复杂度也不同。下面我们开始讨论解决LIS问题的通用套路。

如何求解LIS

求解LIS问题有两种不同的方式,第一种是时间复杂度为$O(n^{2})$的DP,而另一种是基于二分查找维护单调序列的$O(n\log n)$做法。

O(n²)做法

回顾一下LIS问题的一般形式:
给定一个序列$S$,求$S$中一个最长的子序列,使这个子序列满足(严格或不严格均可)单调。
为便于讨论,我们在这里以“最长不降子序列”为例,即子序列满足不严格单调递增。

1 1 2 3 2 2 5 5

Such as 这样一个数列,应用大眼观察法易证最长不降子序列为:

1 1 2 2 2 5 5

长度为7。

由于对于10w规模的数据难以使用大眼观察法,考虑DP。
d[i]为从序列开始到第i个位置的最长不降子序列长度,显然有:
$$ d[i]={\max \limits_{j \in [0,i),a[j] \le a[i]}{\{d[j]\}}} + 1 $$
初始化d[0]=1或不初始化(但需注意细节)。

时间复杂度的证明留给读者作为练习。

O(nlogn)做法

维护一个单调序列,在我们讨论的情景下就是一个不降序列,其长度等于最长不降子序列长度。
如何转化问题?考虑贪心思想。仍然采用上面的例子:

  • a[0]=1,序列中没有元素,直接加入。=> {1}
  • a[1]=1,加入后仍然单调,加入。=> {1,1}
  • a[2]=2 => {1,1,2}
  • a[3]=3 => {1,1,2,3}
  • a[4]=2,注意,直接加入后序列将无法维持单调,我们知道,这时序列中所有数都在这个待加入的2之前,即其中第一个2大(由于是求最长不降子序列,可以允许相等,即搜索严格大于2的数)的数,将其修改为2,能提供的贡献,或者说提供贡献的潜力会比之前大。

正确性证明(!重要):

假设这个修改发生在单调序列的末尾,那么皆大欢喜,用一个较小的数替换较大的,必然能够给之后的数留下更多可安排的空间;另一种情况,这个修改发生在单调序列的中间某个位置,它不会对答案的正确性产生影响,因为我们关注的是长度,而非单调序列本身,能够直接影响单调序列长度的操作只有向末尾加入元素,此时这个修改并没有影响序列末尾数字的大小,不会对后续的判断造成影响,但它安插在单调序列中事实上代表了一种潜力,即子序列的分支,例如对于1 2 3这样的序列,我的子序列既可以先选一个1,也可以先选一个2,我们肯定并保留所有的可能性,即使它用不上。说白了,这是一步远棋,是在为未来可能加入的元素考量。如果这一分支成长到了一定程度(例如最终导致单调序列末尾元素被替换),那么它对答案的贡献才体现出来。

根据上面的分析,这个单调序列中储存的不一定是最长不降子序列(甚至不一定是正确解)。看下面这个例子:

1 2 3 1

请读者自己模拟序列维护的过程。不难发现最后的序列是1 1 3,它虽然与最长不降子序列等长,但甚至不是原序列的子序列!

维护的单调序列只关注长度,结束时序列中并不是求得的最长不降子序列!

请一定注意重点理解这部分内容。

这样转化问题能带来什么好处呢?

不难发现我们需要在直接加入无法维持单调时进行查找,找到要被替代的数(此时不妨@哆来咪·苏伊特(取而代之的蝴蝶(很糟))(逃))。这个过程有一个我们很~熟悉的高效算法可以完成——二分查找,它是$O(\log n)$的!这样的话,总时间复杂度就优化到了$O(n\log n)$!

可我不想写二分 [heimu]说得好像你会一样(嫌弃脸)[/heimu]

没问题,此时需要介绍STL的两个二分姥爷:

lower_bound函数

至少需要传3个参数,前两个跟sort一样,第三个是要查找的元素(先设为x便于叙述),如果有第四个,那就是自定义比较器了。
这个函数比较毒瘤,首先,它默认你给它的是一个(可以不严格)单调递增的序列。降序?没问题,但我们要给它一个greater<>()比较器,否则给你搜到天涯海角去。
然后说说返回值。返回一个指针,指向序列中第一个大于等于x的位置。

其实风格跟sort是一致的(废话),拿返回值减数组首指针就是在数组中的位置。

例子:1 2 2 32就是1 [2] 2 3这个位置。

upper_bound函数

lower_bound一样,唯一的区别是返回的指针指向序列中第一个大于x的位置。

例子:1 2 2 32就是1 2 2 [3]这个位置。

如何解决这道题

扯了老半天,最初的目的还是没达到,你说第一问是个裸的LIS我懂,第二问咋求啊?

其实,还是个LIS。

在我找工具画图的时间里边咱们先口头分析一下为啥。

[heimu]即得易见平凡,仿照上例显然,留作习题答案略,读者自证不难[/heimu]

一堆废铁导弹,我们随便划分一下,就假设k次能全部打下来⑧。(每次要尽力啊,不能说后面有可以打的不打,否则不合题意。)
随便从第1组里边找一颗导弹,第2组里一定有比它飞得高的,否则何必让第2组的小姐姐费事,第1组顺便就给收掉了,根本没第2组事(不严格单调递减啊,能打的要尽量打,不然对不起国防投入)。这样找一个严格单增序列,长度肯定是k
下面把最长上升子序列长度算出来记为m,由前方粗体字显然,$m \ge k$;再从这个最长上升子序列考虑,任意两个元素一定不在同一组内(想一想,为什么?),从而$m \le k$,综上,$m = k$。

于是,这道题就解决了~

$O(n^{2})$做法如下

#include<cstdio>
#include<algorithm>
const int MAXN = 100007;
int a[MAXN],d[MAXN],f[MAXN];
using std::max;
int main(){
    int n=0;
    int ans1=0;
    int ans2=0;
    while(~scanf("%d",&a[n])){
        int t1=0,t2=0;
        for(int i=0;i<n;i++){
            if(a[i]>=a[n])t1=max(t1,d[i]);
            if(a[i]<a[n])t2=max(t2,f[i]);
        }
        d[n]=t1+1;
        f[n]=t2+1;
        ans1=max(ans1,d[n]);
        ans2=max(ans2,f[n]);
        n++;
    }
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}

$O(n \log n)$做法如下

#include<cstdio>//IO
#include<cstring>//memset
#include<algorithm>//max和二分查找 
#include<functional>//greater
const int MAXN = 100007;
int a[MAXN],d[MAXN],f[MAXN];
using std::max;
using std::lower_bound;
using std::upper_bound;
using std::greater;
int main(){
    int n=0;
    int ans1=0;
    int ans2=0;
    memset(d,0,sizeof(d));
    memset(f,0,sizeof(f));
    while(~scanf("%d",&a[n])){
        if(ans1>0&&d[ans1-1]<a[n]){
            int pos=upper_bound(d,d+ans1,a[n],greater<int>())-d;
            //Note: upper_bound和lower_bound均 **只处理升序** 
            //e.g. 1 1 2 2 3 3 4 4 4 5 5 5 
            //我希望查找 4 
            //lower_bound返回序列中第一个 大于等于 __val 的元素指针 
            //这时查找的结果是 位置6 => 3 3 [4] 4 4 5 5 5 
            //upper_bound返回序列中第一个 大于 __val 的元素指针 
            //这时查找的结果是 位置9 => 3 3 4 4 4 [5] 5 5 
            //对降序的处理? 
            //自定义比较器即可,使用 std::greater 即可让这些函数认为3比5大 
            //此处进行二分查找替换维护序列 是为了保持单调性 
            //~~保持单调性的原因留给读者思考~~ 
            //此处为什么用upper_bound? 
            //e.g. 5 5 4 4 3 3 2 2 1 1 
            //此时新加入一个 4 
            //很显然,应该是第一个 **大于** 4 的位置 
            //即 5 5 4 4 [3] 3 2 2 1 1 
            //修改后序列保持不严格单调 
            //~~下面使用lower_bound的正确性证明就留给读者作为练习~~ 
            d[pos]=a[n];
        }else d[ans1++]=a[n];
        if(ans2>0&&f[ans2-1]>=a[n]){
            int pos=lower_bound(f,f+ans2,a[n])-f;
            f[pos]=a[n];
        }else f[ans2++]=a[n];
        n++;
    }
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}

什么?图?哪来的图?有向图还是无向图?(装傻qwq)

好吧其实是这张,相同颜色代表同一组。

第二问示意图

最后修改:2019 年 07 月 14 日 06 : 39 PM

发表评论