这道题和之前的那个一样是分组背包。我发现分组背包的套路都是这样省的:
一般这个题目的dp[ i ][ j ]的意思是以 i 这个节点为根的子树，容纳 j 个***东西所获得的最大价值。
上面的temp是u这个节点的下面的最大子树返回的 那个***的东西的数量（就是 j 那个位置代表的东西）， 然后 sum 这个值是以 u 这个节点为根节点的子树返回的的那个***的值。然后基本的思路就是和分组背包一样，把每个子树看成一组，然后通过子树的组来更新大的组。
然后注意这里的边权，如果要加入以 j 为根节点的子树的***的东西，那么必须要花费从 u -> v 这个的边权的花费。
至于初始化的话基本就是初始化叶子节点的值。
#include<iostream> #include<string> #include<cstring> using namespace std; const int MAXN = 3e3+10; int cost[MAXN]; int dp[MAXN][MAXN]; struct Edge{ int v, next, w; }edge[MAXN]; int head[MAXN]; int cnt; void addEdge(int u, int v, int w){ edge[cnt].v = v; edge[cnt].next = head[u]; edge[cnt].w = w; head[u] = cnt++; return; } void ini(int n, int m) { for(int i = 1; i <= n; i++) head[i] = -1; cnt = 0; // for(int i = 1; i <= n; i++) // { // for(int z = 1; z <= m; z++) // dp[i][z] = -1; // } memset(dp, ~0x3f, sizeof(dp)); for(int i = 1; i <= n; i++) dp[i][0] = 0; return; } int dfs(int u) { int sum; if(cost[u]) sum = 1; else sum = 0; int temp; for(int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].v; temp = dfs(v); sum +=temp; for(int z = sum; z >= 1; z--) { for(int j = 1; j <= z&& j <= temp; j++) { dp[u][z] = max(dp[u][z], dp[u][z-j]+dp[v][j]-edge[i].w); } } } return sum; } int main() { int n, m; cin >> n >> m; ini(n, m); int num1 = n-m; for(int i = 1; i <= num1; i++) { int num2, v, w; cin >> num2; for(int z = 1; z <= num2; z++) { cin >> v >> w; addEdge(i, v, w); } } for(int i = n-m+1; i <= n; i++) { cin >> cost[i]; dp[i][1] = cost[i]; } dfs(1); int ans = 0; for(int i = 1; i <= m; i++) { if(dp[1][i] >= 0) ans = i; } cout << ans; return 0; }
原文：https://www.cnblogs.com/hyb-bbfss/p/14540059.html