蓝桥杯 ALGO-13 导弹拦截
问题描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，为导弹依次飞来的高度
输出格式
两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数
样例输入
389 207 155 300 299 170 158 65
样例输出
6
2
分析：据题意，最多拦截的导弹数即为 最大下降子序列的长度，最少配备的系统数即为 最大上升子序列长度；
介绍一下基本概念：
所谓的子序列就是在原来序列中找出一部分组成的序列，
所谓的递增子序列: 首先它是子序列，其次它们的元素是递增的，也就是说是原来原大的。
最长子序列就是子序列中元素的个数是最多的那一序列。
- 如：dabdbf的最长递增子序列是: abdf
因为要使它是递增又是最长，所以最开始的数要是序内列中最小的，是a, 然后是比它大一点的b,d，由于后第二个b比d小所以不能取过来，这样就成了abdf - 12356710它的递增子序列有很多.
比如：12, 13 , 15, 16, 1356, 137,... - 公共子序列就是子序列的元素必须在两个序列中都要出现，所以
此题的公共子序列是：ab, ag, abg
此题的输入一开始让我很懵。首先用字符串变量获取输入的整行字符串，然后将该字符串通过空格分割成一个字符串数组，之后将字符串数组中每个字符串转换成整型存入整型数组
import java.util.Scanner;
public class Main {
static int[] input,
maxLength,maxCount;
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String[] string = s.split(" ");
input = new int[string.length];
for(int i=0;i<string.length;i++){
input[i] = Integer.parseInt(string[i]);
}
dp(input.length);
int result1 = 0; //表示最多能拦截的导弹数结果
int result2 = 0; //表示最少需要的系统数结果
for(int i=0;i<input.length;i++){
result1 = Math.max(result1, maxLength[i]);
result2 = Math.max(result2, maxCount[i]);
}
System.out.println(result1);
System.out.println(result2);
}
private static void dp(int n){
maxCount = new int[n];
maxLength = new int[n];
for(int i=0;i<n;i++){
maxLength[i] = 1;
maxCount[i] = 1;
for(int j=0;j<i;j++){
if(input[j] > input[i]){
maxLength[i] = Math.max(maxLength[i], maxLength[j]+1);
}else{
maxCount[i] = Math.max(maxCount[i], maxCount[j]+1);
}
}
}
}
}