1044 拦截导弹
1999年NOIP全国联赛提高组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入描述 Input Description
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）
输出描述 Output Description
输出这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例输入 Sample Input
389 207 155 300 299 170 158 65
样例输出 Sample Output
6
2
数据范围及提示 Data Size & Hint
导弹的高度<=30000，导弹个数<=20
分类标签 Tags 点此展开
第一问即经典的最长不下降子序列问题，可以用一般的DP算法，也可以用高效算法，但这个题的数据规模不需要。
用a[x]表示原序列中第x个元素，b[x]表示长度为x的不下降子序列的长度，。当处理第a[x]时，可查找它可以连接到长度最大为多少的不下降子序列后（即与部分b[x]比较）。假设可以连到长度最大为maxx的不下降子序列后，则b[x]:=maxx+1。b数组被赋值的最大值就是第一问的答案。
第二问用贪心法即可。每颗导弹来袭时，使用能拦截这颗导弹的防御系统中上一次拦截导弹高度最低的那一套来拦截。若不存在符合这一条件的系统，则使用一套新系统。
注意这个求的是最长不上升子序列
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=21; 7 const int maxn=0x7fffffff; 8 int a[MAXN][4]; 9 int now=1; 10 int xt[MAXN]; 11 int now2=0;// 系统的数量 12 int main() 13 { 14 while(cin>>a[now][1]) 15 { 16 int flag=0; 17 for(int i=1;i<=now2;i++) 18 { 19 if(xt[i]>=a[now][1]) 20 { 21 flag=1; 22 xt[i]=a[now][1]; 23 break; 24 } 25 26 } 27 if(flag==0) 28 { 29 now2++; 30 xt[now2]=maxn; 31 xt[now2]=a[now][1]; 32 } 33 a[now][2]=1; 34 a[now][3]=0; 35 now++; 36 } 37 for(int i=now-2;i>=1;i--) 38 { 39 int l=0; 40 int k=0; 41 for(int j=i+1;j<=now-1;j++) 42 { 43 if(a[j][1]<a[i][1]&&a[j][2]>l) 44 { 45 k=j; 46 l=a[j][2]; 47 } 48 } 49 if(l>0) 50 { 51 a[i][2]=l+1; 52 a[i][3]=k; 53 } 54 55 } 56 int ans1=0; 57 for(int i=1;i<=now-1;i++) 58 { 59 ans1=max(a[i][2],ans1); 60 } 61 printf("%d ",ans1); 62 printf("%d",now2); 63 return 0; 64 }