题解 1627: 蓝桥杯算法训练VIP-拦截导弹（JAVA Dilworth定理）

解题思路:

Dilworth定理:偏序集的最少反链划分数等于最长链的长度
对于本题来说, 把数列划分成最少的不上升子序列个数等于数列的最长单调增长度
使用线段树O(nlogn)
使用dp O(n2)
注意事项:

参考代码:

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

/*
输入导弹依次飞来的高度（雷达给出的高度数据是\le 50000≤50000的正整数）
计算这套系统最多能拦截多少导弹(最大不上升子序列)，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统(最少不上升子序列个数)。
 */
// https://www.luogu.com.cn/problem/P1020
public class Main {
    static StreamTokenizer cin;
    static PrintWriter out;
    static ArrayList<Integer> list = new ArrayList<>();
    static int[] dp;
    public static void main(String[] args) throws IOException{
        cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        while(cin.nextToken() != StreamTokenizer.TT_EOF)
            list.add((int)cin.nval);
        dp = new int[list.size()];
        Arrays.fill(dp, 1);  // 初始化每个元素初始上升个数为1
        int count = 1;
        for(int i = 0; i < list.size(); i++){  // 以i结尾
            for(int j = 0 ; j < i; j++){
                if(list.get(j) >= list.get(i)){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            count = Math.max(count, dp[i]);
        }
        out.println(count);  // 最多能拦截的导弹数
        Arrays.fill(dp, 1);  // 初始化每个元素初始上升个数为1
        count = 1;
        for(int i = 0; i < list.size(); i++){  // 以i结尾
            for(int j = 0 ; j < i; j++){
                if(list.get(j) < list.get(i)){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            count = Math.max(count, dp[i]);
        }
        out.println(count);
        out.flush();
        out.close();
    }

}