c/c++语言开发共享BZOJ1722: [Usaco2006 Mar] Milk Team Select 产奶比赛(树形dp)

题意

题目链接

sol

挺显然的树形背包吧。。

(f[i][j])表示(i)这棵子树中答案为(j)的最大价值，转移的时候背包一下。。

第一次写树形背包，犯了两个错误

1. 枚举根节点的贡献时需要倒着枚举

2. 转移时需要注意(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"); }