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