动态规划之——拦截导弹 NOIP1999(提高组) 第一题

桃扇骨 2023-08-17 16:50 83阅读 0赞

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

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

【输入文件】missile.in

单独一行列出导弹依次飞来的高度。

【输出文件】missile.out

两行，分别是最多能拦截的导弹数，要拦截所有导弹最少要配备的系统数

【输入样例】

389 207 155 300 299 170 158 65

【输出样例】

【问题分析】

有经验的选手不难看出这是一个求最长非升子序列问题，显然标准算法是动态规划。

以导弹依次飞来的顺序为阶段，设计状态opt\[i\]表示前i个导弹中拦截了导弹i可以拦截最多能拦截到的导弹的个数。

状态转移方程：

opt\[i\]=max(opt\[j\])+1 (h\[i\]>=h\[j\]，0=<j<i) \{h\[i\]存，第i个导弹的高度\}

最大的opt\[i\]就是最终的解。

这只解决了第一问，对于第二问最直观的方法就是求完一次opt\[i\]后把刚才要打的导弹去掉，再求一次opt\[i\]直到打完所有的导弹，但这样做就错了。

不难举出反例： 6 1 7 3 2

错解： 6 3 2/1/7 正解：6 1/7 3 2

其实认真分析一下题就会发现：每一个导弹最终的结果都是要被打的，如果它后面有一个比它高的导弹，那打它的这个装置无论如何也不能打那个导弹了，经过这么一分析，这个问题便抽象成在已知序列里找最长上升子序列的问题。

#include<iostream>
    
    using namespace std;
    
     void missile(int *height,int len)
     {
    	 if(height==NULL || len<=0)
    		 return;
    	 int *longestDecre=new int[len]; //最长的下降子序列，即是求一套系统最多打下的导弹
    	 int *mostNumSet=new int[len];   //最多需要的导弹的套数
    	 int i=0;
    	 for(i=0;i<len;i++)
    	 {
    		 longestDecre[i]=1;
    		 mostNumSet[i]=1;
    	 }
    	 for(i=1;i<len;i++)
    		 for(int j=0;j<i;j++)
    		 {
    			 if(height[i]<=height[j] &&(longestDecre[j]+1>longestDecre[i]))
    				 longestDecre[i]=longestDecre[j]+1;
    			 if(height[i]>height[j] && (mostNumSet[j] +1 > mostNumSet[i]))
    				 mostNumSet[i]=mostNumSet[j]+1;
    		 }
    		 int max1=0,max2=0;
    		 for(i=0;i<len;i++)
    		 {
    			 if(max1<longestDecre[i]) max1=longestDecre[i];
    			 if(max2<mostNumSet[i]) max2=mostNumSet[i];
    		 }
    		 cout<<max1<<endl;
    		 cout<<max2<<endl;
    		 delete[] longestDecre;
    		 delete[] mostNumSet;
     }
    
    
    
     int main(void)
     {
    	 int h[]={389,207,155,300,299,170,158,65}; 
    	 //int h[]={389, 207, 155, 300, 299, 170, 158, 65, 156, 100, 43, 197};
    	 missile(h,8);
    	 return 0;
     }