…
O(nm^2)
https://vijos.org/records/543919bc17f3cade3fb0a871
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | //}/* .................................................................................................................................. */const int N = int(3e2) + 9;VI adj[N]; int f[N][N], val[N];int n, m;void dfs(int u = 0){ ECH(it, adj[u]){ int v = *it; dfs(v); DWN_1(i, m, 1) REP_1(j, i) checkMax(f[u][i], f[u][i-j]+f[v][j]); } DWN_1(i, m, 1) f[u][i] = f[u][i-1] + val[u];}int main(){#ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout);#endif REP_1_C(i, RD(n, m)){ adj[RD()].PB(i); RD(val[i]); } ++m; dfs(); OT(f[0][m]);} |
O(nm)
https://vijos.org/records/5411eea148c5fcdb208b4568
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | //}/* .................................................................................................................................. */const int N = int(3e2) + 9;VI adj[N]; int f[N][N], val[N];int n, m;void dfs(int u = 0){ ECH(it, adj[u]){ int v = *it; REP(i, m) f[v][i] = f[u][i] + val[v]; // 强制在 u 的当前状态（所有 dfs 序在 v 之前的节点所形成的泛化物品）中放入物品 v。。作为 v 的初始状态。。。 dfs(v); REP_1(i, m) checkMax(f[u][i], f[v][i-1]); // 泛化物品的并。。。 }}int main(){ REP_1_C(i, RD(n, m)){ adj[RD()].PB(i); RD(val[i]); } dfs(); OT(f[0][m]);} |
Alca
Amber
Belleve Invis
Chensiting123
Edward_mj
Fotile96
Hlworld
Kuangbin
Liyaos
Lwins
LYPenny
Mato 完整版
Mikeni2006
Mzry
Nagatsuki
Neko13
Oneplus
Rukata
Seter
Sevenkplus
Sevenzero
Shirleycrow
Vfleaking
wangzhpp
Watashi
WJMZBMR
Wywcgs
XadillaX
Yangzhe
三途川玉子
About.me
Vijos
