「LibreOJ NOIP Round #1」旅游路线
题目链接:https://loj.ac/problem/539
题解:
这个题就很神奇
首先大力$dp$很好想,因为可以把一维放到状态里以取消后效性。
然后就能倍增了...因为就是个智障$dp$
我没想出来/px
代码:
#include <bits/stdc++.h> #define N 110 #define M 1010 #define K 30 #define inf 0x3f3f3f3f using namespace std; int g[N][N][K], p[N], c[N], a[N], b[N], w[N][N], f[N][N * N]; char *p1, *p2, buf[100000]; #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ ) int rd() { int x = 0, f = 1; char c = nc(); while (c < 48) { if (c == '-') f = -1; c = nc(); } while (c > 47) { x = (((x << 2) + x) << 1) + (c ^ 48), c = nc(); } return x * f; } int main() { int n = rd(), m = rd(), C = rd(), T = rd(); memset(g, 0xef, sizeof g); for (int i = 1; i <= n; i ++ ) { p[i] = rd(), c[i] = rd(); c[i] = min(c[i], C); g[i][i][0] = 0; } for (int i = 1; i <= m; i ++ ) { int x = rd(), y = rd(), z = rd(); g[x][y][0] = z; } for (int k = 1; k <= 17; k ++ ) { for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= n; j ++ ) { for (int x = 1; x <= n; x ++ ) { g[i][j][k] = max(g[i][j][k], g[i][x][k - 1] + g[x][j][k - 1]); } } } } for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= n; j ++ ) { a[j] = -inf; } a[i] = 0; for (int k = 0; k <= 17; k ++ ) { if((c[i] >> k) & 1) { for (int j = 1; j <= n; j ++ ) { b[j] = -inf; for (int x = 1; x <= n; x ++ ) { b[j] = max(b[j], a[x] + g[x][j][k]); } } for (int j = 1; j <= n; j ++ ) { a[j] = b[j]; } } } for (int j = 1; j <= n; j ++ ) { w[i][j] = a[j]; } } for (int q = 0; q <= n * n; q ++ ) { for (int x = 1; x <= n; x ++ ) { if (q >= p[x]) { for (int y = 1; y <= n; y ++ ) { f[x][q] = max(f[x][q], f[y][q - p[x]] + w[x][y]); } } } } while (T -- ) { int s = rd(), q = rd(), d = rd(); int pl = lower_bound(f[s], f[s] + n * n + 1, d) - f[s]; if (pl > q) { puts("-1"); } else { printf("%d\n", q - pl); } } return 0; }
小结:如果是图上的dp,我们可以考虑直接加上一个维度,使得不会出现后效性。