正因为生来什么都没有,因此我们能拥有一切。(o゚▽゚)o

  • 微信公众号
  • P1020 导弹拦截

    jingyile·2018-11-04·188 次阅读

    题目描述

    某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

    输入导弹依次飞来的高度(雷达给出的高度数据是≤50000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
    输入输出格式

    输入格式:

    1行,若干个整数(个数≤100000)

    输出格式:

    2行,每行一个整数,第一个数字表示这套系统最多能拦截多少导弹,第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
    输入输出样例

    输入样例#1:

    389  207  155  300  299  170  158  65

    输出样例#1:

    6
    2

    说明

    为了让大家更好地测试n方算法,本题开启spj,n方100分,nlogn200分

    每点两问,按问给分,题目来源:洛谷P1020.

    做第二问之前需要知道的一个定理,

    Dilworth定理:对于一个偏序集,最少链划分等于最长反链长度。
    关于Dilworth定理的证明:戳这里!

    在本题中的应用:一个序列中最短下降子序列的个数就等于其最长不下降子序列的长度

    解法一(比较常规的求最长上升/下降子序列,O(n^2)):

    dp解法,状态转移方程为 f[i]=max(f[i],f[j]+1) ,j=i-1到1

    100分代码:

    解法二(利用单调性+二分法,O(n*logn)):

    我们开一个f数组来表示长度为I的上升子链的最小值,用1个ans来记录当前最长链的长度,

    如果a[i]<=f[ans], 则 ans++, f[ans]=a[i];

    否则就二分查找恰好以a[i]为结尾的子链的位置,并判断是否更新它。

    f[i]存储长度为i时该单调序列的结束点。通过下面的举例分析说明。记ans为当前最大标记

    1 - P1020 导弹拦截

    建表详细过程,ans=1,f[ans]=a[ans]=389;

    a[2]<f[ans] ---------> ans=ans+1=2, f[ans]=a[2]=207;

    a[3]<f[ans] ---------> ans=ans+1=3, f[ans]=a[3]=155;

    a[4]>f[ans]------------> f[2]=a[4]=300;

    a[5]>f[ans] -------------> f[3]=a[5]=299; 注意此时相当于更新了ans,因为之前ans更新到了3

    a[6]<f[ans] ------------> ans=ans+1=4, f[ans]=a[6]=170;

    a[7]<f[ans] ------------> ans=ans+1=5, f[ans]=a[7]=158;

    a[8]<f[ans] -----------> ans=ans+1=6, f[ans]=a[8]=65;

    此时,所有数据处理完毕,当前ans值即为最大不上升序列长度,通过表可以很明显的看出来。

    同样的方法画出了第二问的表,过程和上面类似,不啰嗦了
    2 - P1020 导弹拦截

    200分代码:

     

     


    正因为生来什么都没有,因此我们能拥有一切。(o゚▽゚)o

    
    
    查看评论

    Post a new comment

    Post a new comment
    欢迎回来 , [ 修改 ]




    加载中……