https://www.acwing.com/problem/content/10/
需要注意的点就是,f[u][j]实际上是优化过第第二维后的状态表示,原状态表示应该是f[u][i][j]:对于根结点u,考虑其前i个子树,总体积不超过j的最大价值
dfs(root)的递归含义是:以root为根,考虑其所有子树,总体积不超过max_V的最大价值。
import java.util.*; public class Main { static int N = 110; static int[] v = new int[N], w = new int[N]; static int[] h = new int[N], e = new int[N], ne = new int[N]; static int[][] f = new int[N][N]; static int idx = 0; static int n, m; static { Arrays.fill(h, -1); } static void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx ++; } static void dfs(int u) { for (int j = v[u]; j <= m; j ++) f[u][j] = w[u]; // 优化了第二维,省略了i,对于实际上应该:是对于根结点u // 考虑其前i个子树,总体积不超过j的最大价值 for (int i = h[u]; i != -1; i = ne[i]) { int son = e[i]; dfs(son); for (int j = m; j >= v[u]; j --) // 所以这里要倒写 // 考虑前i个子树,给son_i这个子树,k体积,其他j - k体积 for (int k = 0; k <= j - v[u]; k ++) { // 这里的f[son][k],第二位是考虑了son的所有子树的,f[son][son_sons][k] f[u][j] = Math.max(f[u][j], f[u][j - k] + f[son][k]); } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); int root = -1; for (int i = 1; i <= n; i ++) { int vi = sc.nextInt(), wi = sc.nextInt(), pi = sc.nextInt(); v[i] = vi; w[i] = wi; if (pi == -1) root = i; else { add(pi, i); } } dfs(root); System.out.println(f[root][m]); } }