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;
}