[数据结构与算法]DAG上的动态规划——最长路模型

DAG上的动态规划 嵌套矩形 紫书262

题意：有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转X90度）。例如（1,5）可以嵌套在（6,2）内，但不能嵌套在（3,4）中。你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。

分析：矩形间的“可嵌套”关系是一个典型的二元关系，二元关系可以用图来建模。如果矩形X可以嵌套在Y中，则就从X到Y连一条有向边。这个图是无环的，因为一个矩形无法直接或或间接的嵌套在自己的内部。即是求DAG上的最长路径。

状态转移方程

d（i）= max { d（j）+1 | i, j ∈E?}

// Decline is inevitable
// Romance will last forever
// lrj262 DAG模型——嵌套矩形
#include <bits/stdc++.h>
#define mst(a, x) memset(a, x, sizeof(a))
using namespace std;

const int maxn = 1e2 + 10;
int n, edge[maxn][maxn];
int x[maxn], y[maxn];
int d[maxn];        //d[i]表示从结点i出发的最长路长度
int dp(int i) {
    if(d[i]) return d[i];
    d[i] = 1;
    for(int j = 1; j <= n; j++)
        if(edge[i][j] && d[i] <= dp(j) + 1)
            d[i] = dp(j) + 1;
            
    return d[i];
}
void print(int i) {
    cout << i << ' ';
    for(int j = 1; j <= n; j++) {
        if(edge[i][j] && d[i] - 1 == d[j]) {
            print(j);
            break;
        }
    }
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        if(x[i] > y[i])
            swap(x[i], y[i]);
    }
    mst(edge, 0);
    mst(d, 0);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(x[i] < x[j] && y[i] < y[j]) edge[i][j] = 1;
    int ans = 0;
    int p = -1;
    for(int i = 1; i <= n; i++)
        if(dp(i) > ans) {
            ans = dp(i);
            p = i;
        }
    cout << ans << endl;
    print(p);
    cout << endl;
    return 0;
}