嵌套矩形

import java.util.ArrayList;
import java.util.Scanner;

/**
 *嵌套矩形
 */
public class DAG01 {

    static Scanner scan = new Scanner(System.in);
    static int n, ans = 1;
    static int[] dp;
    static boolean[][] graph;
    static ArrayList<rect> list = new ArrayList<>();

    public static void main(String[] args) {
        n = scan.nextInt();
        dp = new int[n + 1];
        graph = new boolean[n + 1][n + 1];
        rect rect = new rect();
        list.add(rect);
        for (int i = 1; i <= n; i++) {
            rect = new rect();
            rect.h = scan.nextInt();
            rect.w = scan.nextInt();
            list.add(rect);
        }
        buildGraph();
        for (int i = 1; i <= n; i++) {
            int max = dfs(i);
            ans = Math.max(max, ans);
        }

        for (int i = 1; i <= n; i++) {
            if (dp[i] == ans) {
                System.out.println(ans);
                printAns(i);
                break;
            }
        }

    }

    static void buildGraph() {//建图
        for (int i = 1; i < list.size(); i++) {
            for (int j = 1; j < list.size(); j++) {
                rect mod = list.get(i);
                rect temp = list.get(j);
                if ((mod.w > temp.w && mod.h > temp.h) || (mod.w > temp.h && mod.h > temp.w)) {
                    graph[i][j] = true;
                }
            }
        }
    }
    static int dfs(int i) {//记忆化搜索
        if (dp[i] > 0)
            return dp[i];
        dp[i] = 1;
        for (int j = 1; j <= n; j++) {
            if (graph[i][j]) {
                dp[i] = Math.max(dp[i], dfs(j) + 1);
            }
        }
        return dp[i];
    }
    static void printAns(int i) {//打印
        System.out.print(i);
        for (int j = 1; j <= n; j++) {
            if (graph[i][j] && dp[i] == dp[j] + 1) {
                printAns(j);
                break;
            }
        }
    }
    static class rect {
        int h;
        int w;
    }
}

嵌套矩形

原文：https://www.cnblogs.com/continued258/p/12459376.html