题解 | #拦截导弹#

import java.util.*;

public class Main {
    static int n;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i ++)
            nums[i] = in.nextInt();

        System.out.println(func1(nums));
        System.out.println(func2(nums));
    }

    // 最多拦截多少个导弹，线性dp
    public static int func1(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];

        for(int i = 1; i <= n; i ++) {
            f[i] = 1;
            for(int j = 1; j < i; j ++) {
                // 高度相等，两颗导弹均可被拦截
                if(nums[i - 1] <= nums[j - 1]){
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }

        int ans = 0;
        for(int i = 0; i <= n; i ++)
            ans = Math.max(ans, f[i]);

        return ans;
    }

    // 最少要多少个系统
    public static int func2(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];

        for(int i = 1; i <= n; i ++) {
            f[i] = 1;
            for(int j = 1; j < i; j ++) {
                // 严格递增，高度相等的可以被拦截，因此算为一个系统
                if(nums[i - 1] > nums[j - 1]){
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }

        int ans = 0;
        for(int i = 0; i <= n; i ++)
            ans = Math.max(ans, f[i]);

        return ans;
    }
}