题目

题目描述

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

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

输入格式

\(1\)行，若干个整数（个数\(\le 100000\)）

输出格式

\(2\)行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

算法分析

有点难表述，我们先看一个例子。

例子

输入数据

10
0 192 100 91 149 146 159 137 17 188

定义三个变量

opt[i]：表示长度为i的不升序列的末位数字最大为opt[i]
opt_n：当前最长不升序列的长度
f[i]：动态规划计算，以第i个导弹结尾的最长不升序列的长度为f[i]

定义一个函数

int s(int i)：二分查找最大的k使得opt[k]>=h[i]

初始值

memset(opt,0,sizeof(opt));
opt[1]=h[1];f[1]=1;

遍历

代码

for(int i=2;i<=n;++i){
    k=s(i);f[i]=k+1; //求最大的k使得opt[k]>=h[i],则f[i]=k+1
    if(f[i]<=opt_n){ //如果f[i]不超过opt_n，则考虑更新opt[f[i]]
        if(opt[f[i]]<h[i]) opt[f[i]]=h[i];
    }else opt_n++,opt[opt_n]=h[i];
}

手算理解：

1. 当i=2,h[i]=192，没有1<=k<=n使得opt[k]>192，那么k=s(i)=0，f[i]=0+1=1。
   此时f[i]>opt_n=0，即 当前方案长度 超过了 opt中已知的最长序列的长度，则需要更新opt（发现了更长的不升序列，补到opt中）。

   opt_n++; //opt_n=1
   opt[opt_n]=h[i] //opt[1]=192

2. 当i=3,h[i]=100，存在最大的k=1使得opt[k]=192>100，那么f[i]=k+1=2。
   此时f[i]>opt_n，更新opt。

   opt_n++; //opt_n=2
   opt[opt_n]=h[i] //opt[2]=100

3. 当i=4,h[i]=91，存在最大的k=2使得opt[k]=100>91，那么f[i]=k+1=3。
   此时f[i]>opt_n，更新opt。

   opt_n++; //opt_n=3
   opt[opt_n]=h[i] //opt[3]=91

4. 当i=5,h[i]=149，存在最大的k=1使得opt[k]=192>149，那么f[i]=1+1=2。
   此时f[i]<opt_n，即 当前方案长度 小于 opt中已知的最长序列的长度；也就是说，前面已经有过长度相同的不升序列。
   需要判断此时h[i]是否大于opt[f[i]]，因为opt要存最大的末位数字。

   if(opt[f[i]]<h[i]) //opt[f[i]]=opt[2]=100<149
       opt[f[i]]=h[i]; //opt[2]=149

依此类推，之后的操作直接给出：

i=6,f[i]=3
opt[1]=192|opt[2]=149|opt[3]=146|opt[4]=  0|opt[5]=  0|opt[6]=  0|

i=7,f[i]=2
opt[1]=192|opt[2]=159|opt[3]=146|opt[4]=  0|opt[5]=  0|opt[6]=  0|

i=8,f[i]=4
opt[1]=192|opt[2]=159|opt[3]=146|opt[4]=137|opt[5]=  0|opt[6]=  0|

i=9,f[i]=5
opt[1]=192|opt[2]=159|opt[3]=146|opt[4]=137|opt[5]= 17|opt[6]=  0|

i=10,f[i]=2
opt[1]=192|opt[2]=188|opt[3]=146|opt[4]=137|opt[5]= 17|opt[6]=  0|

总结

由此可以发现，opt数组是递减的。
因为每个时刻opt[i]都存长度为i的不升序列的末位最大数字，若i<j，opt[i]必定>opt[j]。反证法：若opt[i]<opt[j]，那么为什么opt[i]的值不能为opt[j]这个序列中的第i个元素呢？

得到了opt数组递减之后，就可以用二分查找最大的k使得opt[k]>=h[i]，那么第i个数就可以接在opt[k]之后了，于是f[i]=k+1，然后更新opt数组。

拦截导弹nlogn解法

原文：https://www.cnblogs.com/1024th/p/10422949.html