洛谷p1020 导弹拦截

题目描述

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

输入导弹依次飞来的高度（雷达给出的高度数据是

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1：

389 207 155 300 299 170 158 65

输出样例#1：

6
2
————————————————————————分割线——————————————————————————
第一问：
第一问其实看似没有思路，最多能拦截多少导弹，但其实，再看一下题目，发现这个拦截系统能拦截的导弹高度其实是呈不上升序列的
那么最多能够拦截的很明显就是最长不上升子序列，拿这一问就简单了
不过，平常学的dp做法都是n^2做法，看看数据100000，很明显超时了
所以我这里介绍一种nlogn的做法（其他同理，包括最长不下降子序列等）：
定义一个f数组，其中f[i]表示长度为i不上升子序列的最后一位数
len表示最长不上升子序列长度 初始化len=0；f[0]=1e9 （正的无限大）
那么，如果high[i](1<=i<=number;表示导弹高度）<=f[len] f[++len]=high[i]
什么意思呢？若当前导弹高度小于等于长度为len的不上升子序列的最后一个数，那么代表这个数是可以加入这个子序列的，此时f[len]要更新成为这个数
否则的话，在f[0——len]中间二分，寻找第一个大于等于high[i]的数f[j]，找到以后，再把high[i]加入到此时f[j]末尾
代码如下（有点乱，有压行的行为）：

if(high[i]<=f[len1])f[++len1]=high[i];
        else{
            int l=0,r=len1;
            while(l<r){
                int mid=(l+r)>>1;
                if(f[mid]>=high[i])l=mid+1;
                else r=mid;
            }
            f[l]=max(f[l],high[i]);
        }

第二问：

刚看到第二问，就想到了贪心，不过很明显超时了（毕竟是n方）

那我们可以推一下

假设一个序列为：7 2 3 9 7 2 3 8 n=8

很明显，手推出来需要4个

用柱形图表示如下：

那么序号为：1,3,6为一个，4,5,7为一个，2,8各一个，合起来为四个

若将一组中柱形图顶部连接起来大概若为下图：

那么可以发现每条直线的左端点（若为点则为这个点）呈上升趋势
证明：
用反证法
共ans条直线（ans为答案），dd[i]为第i条直线左端点数值
假设dd[i-1]>=dd[i]，
那么dd[i-1]这个的应该存在于第i条直线上（直线呈不上升趋势），可以用一个拦截系统拦截
所以与题意相矛盾，故证得dd[i-1]<dd[i](2<=i<=n)
所以这个问题就转换成为求最长上升子序列
nlongn的方法在上一问已经说明了，但：注意：f[0]=-1e9（负的无限大）
AC代码：

#include<bits/stdc++.h>
using namespace std;

int number,high[100003],f[100003],dp[100003],len1,len2;

int main(){
    f[0]=1e9;dp[0]=-1e9;
    while(cin>>high[++number]);number--;
    for(int i=1;i<=number;i++){
        if(high[i]<=f[len1])f[++len1]=high[i];
        else{
            int l=0,r=len1;
            while(l<r){
                int mid=(l+r)>>1;
                if(f[mid]>=high[i])l=mid+1;
                else r=mid;
            }
            f[l]=max(f[l],high[i]);
        }
        if(high[i]>dp[len2])dp[++len2]=high[i];
        else{
            int l=0,r=len2;
            while(l<r){
                int mid=(l+r)>>1;
                if(dp[mid]>=high[i])r=mid;
                else l=mid+1;
            }
            dp[l]=min(dp[l],high[i]);
        }
    }
    cout<<len1<<endl<<len2;
    return 0;
}

如果本蒟蒻有没有讲清楚的地方，可以自己画图模拟，或许可以帮助你

（洛谷AC200题纪念）orz

秒客网

洛谷p1020 导弹拦截

题目描述

输入输出格式

相关文章