1260:【例9.4】拦截导弹(Noip1999)

题目来源:http://ybt.ssoier.cn:8088/problem_show.php?pid=1260

1260:【例9.4】拦截导弹(Noip1999)


时间限制: 1000 ms         内存限制: 65536 KB
提交数: 4533     通过数: 1660 

【题目描述】

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

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

 

【输入】

输入导弹依次飞来的高度。

【输出】

第一行:最多能拦截的导弹数;

第二行:要拦截所有导弹最少要配备的系统数。

【输入样例】

389 207 155 300 299 170 158 65

【输出样例】

6
2

例题不怎么详的解:
这是一道十分经典的LIS动规题目,难点和重点在于需要查找多条LIS并进行统计。这题说是dp,实则更像是纯模拟。
我们抽丝剥茧,将本题数学框架讨论如下:
首先我们要求的这个最多能拦截的导弹数,也就是给出序列的LIS,
然后是拦截所有导弹最少要配备的系统数,也就是最少有几条公共子序列存在,注意,每条子序列必须是最优的。
这个最优是什么意思呢?也就是每套系统(每条子序列)必须拦截下最多的导弹(拥有最长最优的长度)。

本题的算法,我借鉴的是书上的解法,这个解法是可以优化空间复杂度的,但是因为我是初学者,所以写出代码后也不大懂优化,只能勉勉强强按书上的来。
第一问可以用dp解,第二问可以用贪心解。

算法分析:
设置a[j]代表原序列中第j个元素,b[j]表示长度为j的LIS,h[k]表示第k个系统当前可拦截导弹的最高高度;
  1. 遍历已输入序列一次,maxx暂存当前导弹高度可用最长LIS的长度值,于是当前输入的导弹会使LIS长度maxx+1,并将此值存入b数组;
  2. 记录最长LIS的长度;
  3. 贪心计算本次导弹由哪一套系统拦截,若当前所有LIS均对当前输入导弹高度不可用,则新增一套系统拦截。
如果没看懂也无妨,后面会详细解释。

重头戏来了。

    先初始化。

 dp部分很简单的:

 

1 maxx=0;
2 for(j=1;j<=i-1;j++)
3  if(a[j]>=a[i]&&b[j]>maxx) maxx=b[j];
4 b[i]=maxx+1;
5 if(b[i]>m) m=b[i];

 

 大概就是每输入一个数,遍历一遍当前序列,找一遍当前可构成的不下降序列。

 当然如果仅仅是这样就只能求出LIS,求不出最少的系统数,于是我们需要一个贪心:

 1 x=0;//当前使用的系统
 2 for(k=1;k<=n;k++)
 3     {
 4         if(h[k]>=a[i])//首先你这个系统你得可用
 5          if(x==0) x=k;
 6          else if(h[k]<h[x]) x=k;//选择当前可拦截高度最低的可用系统拦截
 7     }
 8     if(x==0){
 9         n++;x=n;
10     }
11     h[x]=a[i];

 完美。

 样例代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 10010
#define MOD 2520
#define E 1e-12
/*This is an example*/
int i,j,k,x,n,maxx,m,a[N],b[N],h[N];

using namespace std;
int main()
{
    i=1;n=0;m=0;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(h,0,sizeof(h));
    while(cin>>a[i])
    {
        maxx=0;
        for(j=1;j<=i-1;j++)
         if(a[j]>=a[i]&&b[j]>maxx) maxx=b[j];
        b[i]=maxx+1;
        if(b[i]>m) m=b[i];
        x=0;
        for(k=1;k<=n;k++)
        {
            if(h[k]>=a[i])
             if(x==0) x=k;
             else if(h[k]<h[x]) x=k;
        }
        if(x==0){
            n++;x=n;
        }
        h[x]=a[i];
        i++;
    }
    cout<<m<<endl<<n<<endl;
    return 0;
}

2019-05-03 12:34:13

 

 

 

 

上一篇:保卫农场


下一篇:最大值与最小值