拦截导弹
时间限制: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
求最后结果,容易想到的是构建好表之后for循环求result[i]的最大值
代码如下:
import java.util.Arrays; import java.util.Scanner; public class Main { public static int max(int x,int y) { return x>y?x:y; } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int cases=scanner.nextInt(); int result[]=new int[21]; int p[]=new int[21]; while(cases--!=0) { int m=scanner.nextInt(); Arrays.fill(result, 0); Arrays.fill(p, 0); int i,j; for(i=1;i<=m;i++) { p[i]=scanner.nextInt(); result[i]=1; } for(i=1;i<=m;i++) { for(j=1;j<i;j++) { if(p[i]<p[j]) result[i]=max(result[i], result[j]+1); // System.out.print(result[i]+" "); } // System.out.println(); } int max=0; for(i=1;i<=m;i++) { if(result[i]>max) max=result[i]; } System.out.println(max); } } }
也可以使用下面方法:
import java.util.Scanner; public class Main { public static int max(int x,int y) { return x>y?x:y; } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int cases=scanner.nextInt(); while(cases--!=0) { int m=scanner.nextInt(); int result[]=new int[m+2]; int p[]=new int[m+2]; int i,j; for(i=1;i<=m;i++) { p[i]=scanner.nextInt(); result[i]=1; } for(i=1;i<=m+1;i++) { for(j=1;j<i;j++) { if(p[i]<p[j]||i==m+1)//当i==m+1时在结果result[i](i=1~m)的判断,相当于不论p[i]和p[j]的关系如何,都求最大值,也就是加1运算 result[i]=max(result[i], result[j]+1); //System.out.print(result[i]+" "); } // System.out.println(); } System.out.println(result[m+1]-1); } } }