题目来源: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个系统当前可拦截导弹的最高高度;
- 遍历已输入序列一次,maxx暂存当前导弹高度可用最长LIS的长度值,于是当前输入的导弹会使LIS长度maxx+1,并将此值存入b数组;
- 记录最长LIS的长度;
- 贪心计算本次导弹由哪一套系统拦截,若当前所有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