文件名称：转成二叉树后如何DP?-动态规划-树型DP经典课件
文件大小：4.26MB
文件格式：PPT
更新时间：2024-05-14 23:11:49
动态规划
转成二叉树后如何DP? 状态定义:f[i][j][k]表示以i为根的树上大头吃j个果子的最小难受值之和，k=0表示i的父亲节点由小头吃，k=1则由大头吃。 问题拓展 设左儿子为l, 右儿子为r, Wi是原图上结点i与它父亲的边的难受值。 f[i][j][1] = min{ f[l][k][0]+f[r][j-k][1], f[l][k-1][1]+f[r][j-k][1]+Wi }; f[i][j][0] = min{ f[l][k-1][1]+f[r][j-k][0], f[l][k][0]+f[r][j-k][0], (M>2) f[l][k][0]+f[r][j-k][0]+Wi (M=2) };