P1020 导弹拦截 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • owlAlice
    我说,不要总说楼上的大佬怎样,因为洛谷智能排序之后,你楼上的大佬已经不是你楼上的了
  • 渣旺子
    楼上666
  • Ousmane_Dembele
    楼上的楼上666
  • UrJack
    楼上的楼上的楼上666
  • AKA_刀枪不入
    楼上的楼上的楼上的楼上666
  • 诸君拔剑吧
    楼上的楼上的楼上的楼上的楼上666
  • 块根大佬
    楼上的楼上的楼上的楼上的楼上的楼上666
  • HuangBo
    打破阵型~.~
  • 你好啊,再见
    楼上的楼上的楼上的楼上的楼上的楼上的楼上的楼上666(恢复阵型)
  • Resical
    楼上的楼上的楼上的楼上的楼上的楼上的楼上的楼上的楼上666
作者: Matyr 更新时间: 2017-10-12 16:43  在Ta的博客查看    183  

补一发树状数组的题解。

楼上dalao已经说得很清楚了,这道题就是要求一个最长单调不升子序列和一个最长单调上升子序列。

说白了就是二维偏序,所以很容易想到树状数组来维护最优解。详情见代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[1000000];
int z[1000000];
int lowbit(int x)
{
    return x&-x;
}
int big;
inline int ask(int x)//这是用来求单调上升子序列的
{
    int r=0;
    for(int i=x;i>0;i-=lowbit(i))
        r=max(r,f[i]);
    return r;
}
inline void add(int x,int v)//这也是用来求单调上升子序列的
{
    for(int i=x;i<=big;i+=lowbit(i))
        f[i]=max(f[i],v);
}
inline int que(int x)//这是用来求最长单调不升子序列的
{
    int r=0;
    for(int i=x;i<=big;i+=lowbit(i))
        r=max(r,f[i]);
    return r;
}
inline void psh(int x,int v)//这也是用来求最长单调不升子序列的
{
    for(int i=x;i>0;i-=lowbit(i))
        f[i]=max(f[i],v);
}
int tot;
int a[1000000];
int ans;
int main()
{
    tot=1;
    while(scanf("%d",&a[tot])!=EOF)
    {
        big=max(big,a[tot]);
        z[tot]=a[tot];
        tot++;
    }
    tot--;//读入并统计个数
    for(int i=1;i<=tot;i++)//求最长单升子序列,树状数组中保存的是0~a[i]的最大值
    {
        int x=ask(a[i])+1;
        ans=max(ans,x);
        add(a[i]+1,x);//因为是严格单升所以这里要+1
    }
    memset(f,0,sizeof(f));//清空树状数组,用来求下面的不降子序列
    int num=0;
    for(int i=1;i<=tot;i++)//求最长不降子序列,树状数组里存的是a[i]~inf的最大值
    {
        int x=que(a[i])+1;
        num=max(num,x);
        psh(a[i],x);//因为是不升而不是严格单降所以不用-1或+1
    }
    printf("%d\n%d",num,ans);
    return 0;
}

评论

  • middle_set
    $O(\frac{n^2}{2})
  • middle_set
    貌似打错了,是$O(\frac{n^2}{2})$
  • Pascal周逸非
    厉害!!!
  • Passer1
    长见识
  • YZHX
    涨姿势了
  • 巫神搞比利
    装得一手好逼
  • ljw2005
    厉害厉害,6666。
  • constructor
    楼上是逗吗O(n^2/2)=O(n^2)好吧……
  • 大螺丝
    6666
  • Resical
    厉害了第一次见到这样的O()
作者: cplusplus 更新时间: 2017-11-09 17:41  在Ta的博客查看    107  

n方200分的题解!

只是加了一个常数优化,最坏1/2 n^2,平均效率较高

在朴素n^2算法中,用f[i]储存以i结尾的最长不上升子序列长度,如样例

i 1 2 3 4 5 6 7 8

a 389 207 155 300 299 170 158 65

f 1 2 3 2 3 4 5 6

发现当f的值相同时,越后面的导弹高度越高

用d[i]维护f值为i的最后一个导弹的位置,t记录当前已经求出最长不升子序列长度

递推求f时枚举a[d[t]],a[d[t-1]],。。。,a[d[1]]是否≥当前求的导弹高度,是就更新f

然后根据某定理求出第二问(楼下大佬们说的很清楚)

#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n=0,a[100001],f[100001],d[100001],ans=1,t=0;
int main() {
    while(~scanf("%d",&a[++n]));//读入数据方法
    n--;//n是导弹数,由于某些原因要--
    for(int i=1; i<=n; i++) {
        f[i]=1;
        for(int j=t; j>0; j--)
            if(a[i]<=a[d[j]]) {
                f[i]=f[d[j]]+1;
                break;
            }
        t=max(t,f[i]);
        d[f[i]]=i;//简单的维护过程
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    ans=1;
    t=0;
    for(int i=1; i<=n; i++) {
        f[i]=1;
        for(int j=t; j>0; j--)
            if(a[i]>a[d[j]]) {
                f[i]=f[d[j]]+1;
                break;
            }
        t=max(t,f[i]);
        d[f[i]]=i;
        ans=max(ans,f[i]);
    }
    printf("%d",ans);
}

评论

  • 吹箫童子
    orz orz
  • mobai
    豁然开朗
  • Yubestor
    代码打不开=-=
  • Runewrz
    (3)中有一个小的手误,应该把最后面的 P>=K 改为 P<=K 。
  • 单身贵族1123
    网站打不开怎么办,在线等急
  • 小白1548555
    66666 豁然开朗,膜大佬
  • isunny
    %%%
  • Eric_hoo
    666666
  • Eric_hoo
    大佬
  • ZhYic
    终于明白。Orz
作者: JJPJJ 更新时间: 2017-12-27 13:56  在Ta的博客查看    96  

题目链接:导弹拦截


题意总结:

给出一个长度不超过100000的数列,其中的数每个是不大于50000的正整数,求这个数列的最长不降子序列(问一)以及将这个数列划分为n个不降子序列时,n的最小值(问二)。


思路:

1、对于问一直接用O(n*logn)的方法求最长不升子序列即可。

求不升子序列的方法:

http://https://www.luogu.org/blogAdmin/article/edit/20362

2、对于问二求整个数列的最长上升子序列即可。证明如下:

(1)假设打导弹的方法是这样的:取任意一个导弹,从这个导弹开始将能打的导弹全部打完。而这些导弹全部记为为同一组,再在没打下来的导弹中任选一个重复上述步骤,直到打完所有导弹。

(2)假设我们得到了最小划分的K组导弹,从第a(1<=a<=K)组导弹中任取一个导弹,必定可以从a+1组中找到一个导弹的高度比这个导弹高(因为假如找不到,那么它就是比a+1组中任意一个导更高,在打第a组时应该会把a+1组所有导弹一起打下而不是另归为第a+1组),同样从a+1组到a+2组也是如此。那么就可以从前往后在每一组导弹中找一个更高的连起来,连成一条上升子序列,其长度即为K;

(3)设最长上升子序列长度为P,则有K<=P;又因为最长上升子序列中任意两个不在同一组内(否则不满足单调不升),则有

P>=K,所以K=P。

评论

  • Wilber
    orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz
  • rememberain
    膜拜dalao
  • Okitazero
    这么厉害的吗2333
  • chaos—moon
    膜拜 膜拜
  • futaba
    哈哈哈
  • futaba
    66666666666666
  • futaba
    66666666666666
  • Frozen_land
      ┏┓   ┣┫ ┏┳┫┣┳┓ ┃    ┃
  • futaba
    哥 加油!!! 祝你考试顺利!!
  • futaba
    我这样的渣渣不知到该说什么话呢
作者: H_Bryan 更新时间: 2018-08-05 15:09  在Ta的博客查看    87  

STL大法好!!!

先介绍两个STL函数:lower_bound(), upper_bound()


ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val) 返回的是非降序列的第一个>=key的数的地址(指针)(别问我为什么叫lower_bound,我也不知道);

ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val) 返回的是非降序列的第一个>key的数的地址;

详情见下图

lower_bound(),upper_bound()


再来分析这道题,楼上大佬分析的无比清楚,直接维护一个非升序列和一个非降序列,维护的过程就能用上面两个神奇的STL(当然非升序列的upper_bound()要重载cmp)。不多说,上代码

#include<bits/stdc++.h>
using namespace std;
int a[100005],f[100005],l[100005];
struct cmp{bool operator()(int a,int b){return a>b;}};
int main()
{
    int n=1;
    while(cin>>a[n])n++;
    n--;
    int con=1,cont=1;
    l[1]=f[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(l[cont]>=a[i])l[++cont]=a[i];
        else l[upper_bound(l+1,l+cont+1,a[i],cmp())-l]=a[i];
        if(f[con]<a[i])f[++con]=a[i];
        else f[lower_bound(f+1,f+con+1,a[i])-f]=a[i];
    }
    cout<<cont<<" "<<con;
    return 0;
}

评论

  • 真·五河士道
    前来感恩! 本人弱鸡萌新一枚,刚入门动规,像这种题完全写不出来,但看了大佬的题解后瞬间明白了,多谢大佬! ps:可不可以顺便教我一下,为什么第二问中的定理可以理解为求最长不下降子序列?
  • Chevalier
    OTZ
  • jiang25262
    为什么用树状数组只有100分呢
  • wlyy
    orz
  • 秋木苏
    文末完整代码那里树状数组部分标题是【O(n²)树状数组】,但应该是【O(nlogn)树状数组】?
  • 秋木苏
    文末完整代码处,树状数组部分,主函数的注释有一行“查询以小于等于x的数为【开头】的最长不上升子序列的长度的最大值”,是否应为【结尾】呀?quq
  • 秋木苏
    我错惹!!应该是把query函数注释的【结尾】改成【开头】?
  • QQ893531942
    嗯,这是一篇很认真的评论
  • TwxAqu
    楼上666
  • 大头冲锋车丶
    为什么我用nlogn写的最长上升子序列在第二问是错的?
作者: Sleepy_Piggy 更新时间: 2018-02-11 16:13  在Ta的博客查看    37  

嗯,这是一篇很认真的题解

推荐一篇博客 来自dalao的题解 为数不多的树状数组题解里面写的比较清楚的一篇。

  • 题目有说明:“n方100分,nlogn200分” 这里两种做法都会讲到

第一问很明显是求最长不上升子序列,利用dp的思想,我们设f[i]为以第i个数为开头的最长不上升子序列的长度,然后可以得到这样一段程序

for(int i=n;i>=1;i--){//注意!!因为它是以i开头的最长不上升子序列,所以这里要从n开始循环,不然会出现一些奇妙的bug 
        f[i]=1;//以第i个数为开头的最长不上升子序列的长度至少为1(当这个序列只有它本身这一个数) 
        for(int j=i+1;j<=n;j++){//用前面已经算好的来算现在正在算的这一个 
            if(a[j]<=a[i])//如果a[j]>a[i]的话就不满足不上升这个要求(毕竟a[j]在a[i]后面) 
                f[i]=max(f[i],f[j]+1); //更新f[i]~记得要+1啊 
        }
        ans1=max(ans1,f[i]);//更新ans1 
    }

但是很明显,这段代码的时间复杂度是$O(n^2)$,没能达到$O(n logn)$

仔细想想,可以用树状数组啊ovo。用数值做下标,维护长度最大值,从后往前循环,每次查询之前已经放到树状数组里面的数中以这个数结尾的最长不上升子序列的长度的最大值,然后把这个最大值+1作为以自己结尾的最长不上升子序列的长度,放到树状数组里面。这不就很美滋滋了吗(手动滑稽)。详见代码:

for(int i=n;i>=1;i--){//从后往前循环
        int q=query(a[i])+1;//查询以小于等于x的数为开头的最长不上升子序列的长度的最大值
        add(a[i],q);//这个最大值+1就是以当前这个数开头的最长不上升子序列的长度,丢到树状数组里面去 
        ans1=max(ans1,q);
    }
    printf("%d\n",ans1);

add和query在文末的完整代码中有

嗯就这样,第一问的时间复杂度就已经降到$O(n logn)$了


第二问要用到一个Dilworth定理(Will爷万岁!!!)

Dilworth定理:偏序集的最少反链划分数等于最长链的长度

说简单点其实就是第二问相当于求最长上升子序列,很自然地又想到了dp。这次f[i]表示以i结尾的最长上升子序列的长度,然后就有了这样一段$O(n^2)$的代码

for(int i=1;i<=n;i++){//同上,因为它是以i结尾的最长上升子序列,所以这里要从前往后,不然会出现一些奇妙的bug
        f[i]=1;//以第i个数结尾的最长上升子序列的长度至少为1(当这个序列只有它本身这一个数) 
        for(int j=1;j<i;j++){
            if(a[j]<a[i])//如果a[j]>=a[i]的话就不满足上升这个要求(毕竟a[j]在a[i]前面) 
                f[i]=max(f[i],f[j]+1);//更新f[i]~记得要+1啊 
        }
        ans2=max(ans2,f[i]);//更新ans2 
    }

比较一下,是不是和第一问的dp代码很呢?

和第一问是一样的道理,如果要降到$O(n logn)$的复杂度,我们还是选择树状数组。用数值做下标,维护长度最大值,从前往后循环,每次查询之前已经放到树状数组里面的数中以这个数结尾的最长上升子序列的长度的最大值,然后把这个最大值+1作为以自己结尾的最长不上升子序列的长度,放到树状数组里面。代码:

memset(f,0,sizeof(f));//还是memset一下比较保险 
    for(int i=1;i<=n;i++){//从前往后循环 
        int q=query(a[i]-1)+1;//查询以小于(没有等于!!!)x的数为结尾的最长上升子序列的长度的最大值
        add(a[i],q);//这个最大值+1就是以当前这个数结尾的最长上升子序列的长度,丢到树状数组里面去 
        ans2=max(ans2,q);
    }

搞定辣!!! 完整代码:

  • $O(n^2)$ dp
#include<cstdio>
#include<algorithm>

using namespace std;
int n,ans1,ans2,f[100001],a[100001];

int main(){
    while(scanf("%d",&a[++n])!=EOF);
    n--;//要-1,不然n就不是正确的n了 
    for(int i=n;i>=1;i--){//注意!!因为它是以i开头的最长不上升子序列,所以这里要从n开始循环,不然会出现一些奇妙的bug 
        f[i]=1;//以第i个数开头的最长不上升子序列的长度至少为1(当这个序列只有它本身这一个数) 
        for(int j=i+1;j<=n;j++){//用前面已经算好的来算现在正在算的这一个 
            if(a[j]<=a[i])//如果a[j]>a[i]的话就不满足不上升这个要求(毕竟a[j]在a[i]后面) 
                f[i]=max(f[i],f[j]+1); //更新f[i]~记得要+1啊 
        }
        ans1=max(ans1,f[i]);//更新ans1 
    }
    for(int i=1;i<=n;i++){//同上,因为它是以i结尾的最长上升子序列,所以这里要从前往后,不然会出现一些奇妙的bug
        f[i]=1;//以第i个数结尾的最长上升子序列的长度至少为1(当这个序列只有它本身这一个数) 
        for(int j=1;j<i;j++){
            if(a[j]<a[i])//如果a[j]>=a[i]的话就不满足上升这个要求(毕竟a[j]在a[i]前面) 
                f[i]=max(f[i],f[j]+1);//更新f[i]~记得要+1啊 
        }
        ans2=max(ans2,f[i]);//更新ans2 
    }
    printf("%d\n%d\n",ans1,ans2);
}
  • $O(n^2)$树状数组
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
int n,maxn,ans1,ans2,f[1000001],a[1000001];

int lowbit(int x){return x&-x;}

void add(int x,int c){ 
    for(int i=x;i<=maxn;i+=lowbit(i)) f[i]=max(f[i],c);//维护最大值 
}

int query(int x){
    int res=0;
    for(int i=x;i>=1;i-=lowbit(i)) res=max(res,f[i]);//求以小于等于x的数为结尾的最长不上升子序列的长度的最大值 
    return res;
}

int main(){
    while(scanf("%d",&a[++n])!=EOF) maxn=max(maxn,a[n]);
    n--;//要-1,不然n就不是正确的n了 
    for(int i=n;i>=1;i--){//从后往前循环 
        int q=query(a[i])+1;//查询以小于等于x的数为开头的最长不上升子序列的长度的最大值
        add(a[i],q);//这个最大值+1就是以当前这个数开头的最长不上升子序列的长度,丢到树状数组里面去 
        ans1=max(ans1,q); 
    }
    printf("%d\n",ans1);
    memset(f,0,sizeof(f));//还是memset一下比较保险 
    for(int i=1;i<=n;i++){//从前往后循环 
        int q=query(a[i]-1)+1;//查询以小于(没有等于!!!)x的数为结尾的最长上升子序列的长度的最大值
        add(a[i],q);//这个最大值+1就是以当前这个数结尾的最长上升子序列的长度,丢到树状数组里面去 
        ans2=max(ans2,q);
    }
    printf("%d\n",ans2);
}