题意
题目链接
sol
挺显然的树形背包吧。。
(f[i][j])表示(i)这棵子树中答案为(j)的最大价值,转移的时候背包一下。。
第一次写树形背包,犯了两个错误
-
枚举根节点的贡献时需要倒着枚举
-
转移时需要注意(k = 0)的情况,不要出现重复转移
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1001, inf = 1e9 + 7; inline int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, x, a[maxn], siz[maxn], f[maxn][maxn], g[maxn][maxn]; vector<int> v[maxn]; void dfs(int x, int fa) { siz[x] = 1; f[x][0] = g[x][0] = 0; for(int i = 0, to; i < v[x].size(); i++) { if((to = v[x][i]) == fa) continue; dfs(to, x); siz[x] += siz[to]; for(int j = siz[x]; j >= 0; j--) {//倒着转移避免更新到重复状态 for(int k = 0; k <= siz[to]; k++) { g[x][j] = max(g[x][j], g[x][j - k] + max(f[to][k], g[to][k]));//不选 //g[x][j] = max(g[x][j], g[x][j - k] + g[to][k]); //g[x][j] = max(g[x][j], g[x][j - k] + f[to][k]); 这里不要分开写,否则k = 0的时候会出现重复的情况 if(k > 0) f[x][j] = max(f[x][j], f[x][j - k] + f[to][k - 1]);//选 f[x][j] = max(f[x][j], f[x][j - k] + g[to][k]); } } } for(int i = 0; i <= siz[x]; i++) f[x][i] += a[x]; } main() { // freopen("7.in", "r", stdin); n = read(); x = read(); memset(f, -0x3f, sizeof(f)); memset(g, -0x3f, sizeof(g)); for(int i = 1; i <= n; i++) { a[i] = read(); int fa = read(); v[i].push_back(fa); v[fa].push_back(i); } dfs(0, -1); int ans = -1; for(int j = n; j >= 0; j--) if(g[0][j] >= x) return printf("%d", j), 0; puts("-1"); }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607187.html