拦截导弹

时间限制：

3000 ms  |  内存限制：

65535 KB

难度：

3

 

描述

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

 

输入

第一行输入测试数据组数N（1<=N<=10）

接下来一行输入这组测试数据共有多少个导弹m（1<=m<=20）

接下来行输入导弹依次飞来的高度，所有高度值均是大于0的正整数。

输出

输出最多能拦截的导弹数目

样例输入

28389 207 155 300 299 170 158 65388 34 65

样例输出

62

【问题分析】

方法一：

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

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

状态转移方程：       

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

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

代码如下：

1 #include
       
         2 #include
        
          3 int main() 4 { 5  int t,n,max,i,ans,j,a[25],count,opt[25]; 6  scanf("%d",&t); 7  while(t--) 8  {   9   ans=0;10   memset(opt,0,sizeof(opt));//把所有的都opt都变成011   scanf("%d",&n);12   for(i=0;i
         
          <= i-1;j++)//每次都从第一个开始判断，判断到小于i,17    {18     if(a[j]>a[i] && opt[j]+1>opt[i])//当出现后一个小于前一个时，那个数所在的长度加上一，后面的这个判断不能省，具体原因如下19     {20      opt[i]=opt[j]+1;21     }22    }23   }24   for(i=0;i
          
           ans)//筛选出长度最大的那一个26     ans=opt[i];27   printf("%d\n",ans+1);28  }29  return 0;30 }
          
         
        
       

 

当出现8 7 9 6  所对应的长度如下

        0 1 0 ？假如不省的话应该是2，如果省会变成3的，这样的话就错误了；

当执行一次时6小于8,6的位置变成了1，再一次执行6小于7，并且opt[j]+1=2,而opt[i]=1,所以继续执行，

当和9比较时9的位置为0，即opt[j]+1=1依然小于2，所以下面的不再这行了，所以必须要有这一个判断

 

方法二：转移到另一个数组中

有一组特殊数据 7 6 5 6 5结果应该是3 而错误的是4

 AC程序

1     #include
       
         2     #include
        
          3     int main() 4     { 5       int i,j,k,t,a[25],b[25],n,m,f; 6       scanf("%d",&t); 7       while(t--) 8       { 9       memset(b,0,sizeof(b));10         scanf("%d",&n);11       for(i=0;i
         
          b[j] && j==0 )22                                { b[j]=a[i];break;}23                            else if(a[i]>b[j] && a[i]
         
        
       

 

错误的写法

1 #include
       
         2 #include
        
          3 int main() 4 { 5  int i,j,k,t,a[25],b[25],n,m; 6  scanf("%d",&t); 7  while(t--) 8  {  9      memset(b,0,sizeof(b));10        scanf("%d",&n);11   for(i=0;i
         
          b[j])//如果这一步出现替换将会出现7 6 6 5，所以是422                         { b[j]=a[i];break;}23         }24     }25     printf("%d\n",m);26   }27  return 0;28 }