ny79 拦截导弹

拦截导弹

时间限制：3000 ms | 内存限制：65535 KB

难度：3

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

输入

第一行输入测试数据组数N（1<=N<=10）
接下来一行输入这组测试数据共有多少个导弹m（1<=m<=20）
接下来行输入导弹依次飞来的高度，所有高度值均是大于0的正整数。

输出

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

样例输入

2
8
389 207 155 300 299 170 158 65
3
88 34 65

样例输出

6
2

【问题分析】

方法一：

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

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

状态转移方程：

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

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

代码如下：

 1 #include<stdio.h>
 2 #include<string.h>
 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都变成0
11   scanf("%d",&n);
12   for(i=0;i<n;i++)
13    scanf("%d",&a[i]);
14   for(i=1;i<n;i++)
15   {
16    for(j=0;j <= 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<n;i++)
25    if(opt[i]>ans)//筛选出长度最大的那一个
26     ans=opt[i];
27   printf("%d
",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<stdio.h>
 2     #include<string.h>
 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<n;i++)
12        scanf("%d",&a[i]);
13           b[0]=a[0];
14           for(i=1,m=1;i<n;i++)
15         {
16              if(a[i]<b[m-1])
17               b[m++]=a[i];
18              else
19                  {
20                  for(j=0;j<m;j++)
21                             if(a[i]>b[j] && j==0 )
22                                { b[j]=a[i];break;}
23                            else if(a[i]>b[j] && a[i]<b[j-1])
24                                  { b[j]=a[i];break;}
25                }
26         }
27                // for(i=0;i<m;i++)
28                // printf("%d ",b[i]);
29                  printf("%d
",m);
30       }
31      return 0;
32     }

错误的写法

 1 #include<stdio.h>
 2 #include<string.h>
 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<n;i++)
12        scanf("%d",&a[i]);
13             b[0]=a[0];
14       for(i=1,m=1;i<n;i++)
15    {
16            if(a[i]<b[m-1])
17                     b[m++]=a[i];
18         else
19        {
20            for(j=0;j<m;j++)
21                     if(a[i]>b[j])//如果这一步出现替换将会出现7 6 6 5，所以是4
22                         { b[j]=a[i];break;}
23         }
24     }
25     printf("%d
",m);
26   }
27  return 0;
28 }