题解 | #拦截导弹#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
//寻找输入的导弹高度可以划分为几个递减数列
//一个序列中不上升子序列的最小覆盖数等于子序列中最长上(不包括等于)升序列的长度
    public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    // 注意 hasNext 和 hasNextLine 的区别
    //处理输入
    int len = in.nextInt();
    int [] arr = new int[len];
    for(int i=0; i<len; i++){
        arr[i] = in.nextInt();
    }
    solution(len,arr);
    }
    //处理函数
    public static void solution(int len,int[] arr){
        //线性dp，假设以第i个为临界条件
        int [] dp = new int [len+1];
        dp[1] = 1;
        int maxT = 1;
        for(int i =2 ; i<= len ; i++ ){
            //找到邻近得到比其高度高的导
            dp[i] = 1;
            for(int j = 1; j<i;j++){
                if(arr[i-1]<=arr[j-1]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
        }
        maxT = Math.max(maxT,dp[i]);
        }
        //最多拦截导弹的数目
        System.out.println(maxT);

        //怎么求需要多少个呢
        boolean [] num = new boolean [len];
        //计算拦截的数目
        int count = 0;
        //计算发射导弹的数目
        int shit = 0;
        while(count < len){
            shit++;
            int hight =0;
            for(int i = 0; i<len; i++ ){
                if(num[i] == false){
                    hight = arr[i];
                    break;
                }
            }
            for(int j =0 ; j<len ;j++){
                if(num[j] == false&&arr[j]<=hight){
                    num[j]=true;
                    count++;
                    hight = arr[j];
                }
            }
        }
        System.out.println(shit);
    }
}