题目描述

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

输入描述 Input Description

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）

输出描述 Output Description

输出这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例输入 Sample Input

389 207 155 300 299 170 158 65

样例输出 Sample Output

6

2

数据范围及提示 Data Size & Hint
导弹的高度<=30000，导弹个数<=20

分析：

第一问是求最长不上升序列，通过状态转移方程：

dp[j]=1(j← 0 to 导弹个数-1)
dp[j]=max{dp[j],dp[k]+1}(high[k]>=high[j])
再看第二问，求的是最少分几个最长不上升序列。接下来要涉及到一个优美的定理（不要问为什么优美）。

Dilworth定理：对于一个偏序集，最少链划分等于最长反链长度。

Dilworth定理的对偶定理：对于一个偏序集，其最少反链划分数等于其最长链的长度。

也就是说把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度。

因此第二问的状态转移方程是：

dp2[j]=1(j← 0 to 导弹个数-1)

dp2[j]=max{dp2[j],dp2[k]+1}(high[k]<=high[j])

参考文献

要求最少的覆盖，按照Dilworth定理

最少链划分 = 最长反链长度

所以最少系统 = 最长导弹高度上升序列长度。

java 代码

import java.util.Scanner;
public class Main{
    /*
     * *第一问 直接求最长不上升子序列
        第二问 法1 贪心 或者 法2 利用dilworth定理求最长上升子序列
        法1
        从前往后扫描每个数，对于每个数：
        - 情况1：如果现有的子序列的结果都小于当前数， 则创建新子序列
        - 情况2: 将当前数放到结尾大于等于它的最小的子序列后面
     */
    public static void main(String[] agrs) {
        Scanner sc = new Scanner(System.in);

        int[] str = new int[1000];
        String[] arr = sc.nextLine().split(" ");
        int n = arr.length;
        for (int i = 0; i < arr.length; i++) {
            str[i] = Integer.parseInt(arr[i]);
        }
        int[] dp = new int[n + 1];
        int[] dp2 = new int[n + 1];
        int max = 0, min = 0;
        int[] f = new int[n + 1];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            dp2[i] = 1;
            for (int j = 0; j < i; j++) {
                if (str[i] <= str[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                //法二：
                if (str[i] >= str[j]) {
                    dp2[i] = Math.max(dp2[i], dp2[j] + 1);

                }
            }
            max = Math.max(max, dp[i]);
            min = Math.max(min, dp2[i]);
            // 第二问 法1 贪心
            /*
             int k=0; 
             while(k<cnt && f[k]<str[i])
                    k++;
             if(k==cnt) {
                f[cnt++]=str[i];
             }else {
                 f[k]=str[i]; 
             }
             第二问结果为cnt
             */
        }
        System.out.println(max);
        System.out.println(min);
    }
}