导弹拦截（数据加强版）-白红宇

导弹拦截（数据加强版）

阅读量：4364 次

发布时间：2019-06-07

本文共 3575 字，大约阅读时间需要 11 分钟。

题目描述

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

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

输入输出格式

输入格式：

$11行，若干个整数（个数\le 100000≤100000）$

输出格式：

输入输出样例

输入样例#1：

389 207 155 300 299 170 158 65

输出样例#1：

说明

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

每点两问，按问给分

解析：

　　这题相信大家应该都做过，只是这题多加了一问。

　　原题是只求最大拦截数，只需求最长不上升子序列。水水的题目，加上另一问求最少需要的系统数，就变成了普及+了。但还是不难，其实只是再求一个最长不下降子序列。

　　真正的难度是他的数据量！！！

　　那么如何分析呢？

　　见样例：

　　　   389 207 155 300 299 170 158 65 　　　T [1] [2] [3] [4] [5] [6] [7] [8] 　　最长不上升子序列就是取前面比当前的值大，且长度最长的数； 　　用F[]来表示到取到第i个数所能得到的最大长度，T[]储存原始数值； 　　递归式就是：F[i]=max(F[i],F[j]+1);(T[j]>=T[i]&&j

1 for(i=1;i<=n;++i)//第一问 2 {3    F[i]=1;//每一个序列最少也能拦截一个导弹4    for(int j=1;j
     
      <=T[j])F[i]=max(F[i],F[j]+1);5    ANS1=max(ANS1,F[i]);//用ANS1储存第一问的答案6 }

　　我们看一下样例的拦截个数：

　　F [1] [2] [3] [4] [5] [6] [7] [8]

　　　 1　2 3 2 3 4 5 6

　　在3 -> 4 的时候 F[i]的值便小了，而T[3]=155,T[4]=300

　　好像和所需的系统个数是一样的咧！

　　那么遵循“大胆猜测，从不证明的原则” 我们自己手动推测几个数据，发现“k=最长不下降子序列的长度”这一猜想是正确的！！。

　　那问题就简单了！我们只需求出最长不下降子序列就可以了！！

　　状态转移方程式 F[i]=max(F[i],F[j]+1);(T[i]<T[j]&&j>i)

　　代码实现：

1 memset(F,0,sizeof(F));//要清除一下F[]2 for(i=n;i>=1;--i)　　//问题二3 {4     F[i]=1;5     for(int j=n;j>i;--j)if(T[i]

　　那么完整代码如下：

// 这个代码可以得100分，总分200分；#include
     
        #include
      
       #include
       
        #include
        
         using namespace std;int T[100000],F[100000];int main(void){    //freopen("in.txt","r",stdin); //在本地测试时使用     int i=1;    while(scanf("%d",&T[i])==1)i++;    int n=i-1,ANS1=0,ANS2=0;    for(i=1;i<=n;++i)//第一问 ，求最长不上升子序列    {        F[i]=1;        for(int j=1;j
         
          <=T[j])F[i]=max(F[i],F[j]+1);        ANS1=max(ANS1,F[i]);    }    memset(F,0,sizeof(F));//清除F[]    for(i=n;i>=1;--i)//第二问，求最长不下降子序列    {        F[i]=1;        for(int j=n;j>i;--j)if(T[i]

以上是普及组需要的程度！！！接下来讲提高组！！！

这题的数据是加强版的，所以上述方法是不行滴！

那么要怎么办呢？？？

此处就需要学习一下树状数组这密西！！！推荐博客：　　

看完树状数组，我们来讲一下具体实现！！！

先上代码：

1 //加强版数据 200分 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 using namespace std; 8 long long w[100008],f[100008], maxn=0; 9 inline long long lowbit(long long x)  //lowbit函数，具体干嘛详见：https://blog.csdn.net/bestsort/article/details/8079653110 {11     return x&(-x);12 }13 inline void Add_Tree(long long x,long long  y) //将当前序列长度插入树状数组中14 {15     for(long long i=x; i<=maxn; i+=lowbit(i)) f[i]=max(f[i],y);16 }17 inline long long Query_Tree(long long x)//查询大于x的最大长度！！！18 {19     long long Ans=0;20     for(long long i=x; i>=1; i-=lowbit(i)) Ans=max(Ans,f[i]);21     return Ans;22 }23 int main(void)24 {25     //freopen("in.txt","r",stdin);  // 本地输入时必备26     long long n=1,Ans1=0,Ans2=0;  // n为导弹总个数，ANS1为27     while(scanf("%d",&w[n])!=EOF)28         maxn=max(maxn,w[n]),n++;  // 用maxn存储导弹最大高度29     n--;30     for(long long i=n; i>=1; --i) // 从后往前寻找最长不下降子序列31     {32         long long T=Query_Tree(w[i])+1; // 寻找到第i个导弹最大拦截数33         Add_Tree(w[i],T);// 把当前长度加入树状数组中34         Ans1=max(Ans1,T);// ANS1为第一问答案35     }36     memset(f,0,sizeof(f));37     for(long long i=1; i<=n; ++i)// 从前往后寻找最长下降子序列38     {39         long long T=Query_Tree(w[i]-1)+1;//注意 w[i]-1，因为是在找最长下降子序列40         Add_Tree(w[i],T);41         Ans2=max(Ans2,T);//Ans2为第二问42     }43     printf("%lld\n%lld",Ans1,Ans2);//输出44     return 0;45 }

转载于:https://www.cnblogs.com/Blacktears/p/9792841.html

你可能感兴趣的文章