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

CF4D Mysterious Present ?用bool存储是否有边

题目链接

最长路例题

像这种DAG上的最短路 往往只需要记录是否存在边 故可以用bool节省空间，该题用bool就可以过 而用int就会MLE

?

// Decline is inevitable
// Romance will last forever
#include <bits/stdc++.h>
#define mst(a, x) memset(a, x, sizeof(a))
#define int long long
using namespace std;
const int maxn = 5e3 + 1;
int n, w, h;
int wi[maxn], hi[maxn];
int d[maxn];
bool ok[maxn];
int p;
bool edge[maxn][maxn];
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 && ok[j])
            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[j] == d[i] - 1 && ok[j])
        {
            print(j);
            break;
        }
    }
}
signed main() {
    cin >> n >> w >> h;
    mst(ok, 1);
    p = n;
    for(int i = 1; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        if(u <= w || v <= h) ok[i] = 0;
        wi[i] = u;
        hi[i] = v;
    }
    for(int i = 1; i <= p; i++)
        for(int j = 1; j <= p; j++) {
            if(ok[i] == 0 || ok[j] == 0) continue;
            if(wi[i] < wi[j] && hi[i] < hi[j])
                edge[i][j] = 1;
        }
    int len = 0;
    int best = -1;
    for(int i = 1; i <= p; i++) {
        if(ok[i] == 1 && dp(i) > len) {
            len = d[i];
            best = i;
        }
    }
    if(!len) cout << 0 << endl;
    else {
        cout << len << endl;
        print(best);
        cout << endl;
    }
    return 0;
}