传送门
关于如何把多叉树转化为二叉树，有个口诀，叫做左儿子不变，右儿子兄♂弟。
详细的不多说，可以去参考一下相关资料。
等转化为二叉树了过后，让我们来琢磨一下。
左儿子：原根节点的孩子。
右儿子：原根节点的兄 ♂贵 。
也就是说，不能直接套用第一题的方程，但是可以对dp数组进行相同的定义。
对于一个根节点，都可以，选，或者，不选。
当给左儿子分配资源时，根节点必须选，而与右儿子无关。
因此，方程就显而易见了，dp[i][j]=max(dp[i][j],dp[i.rson][j],dp[i.lson][k]+dp[i.rson][j-k-1]+val[i]) (0<=k<j)
//dp[i][j]: i的所有兄弟和i的所有儿子 和i自己 学j门课的最大学分总和。 //dp[i][j]=max(dp[rson][j],dp[lson][k]+dp[rson][j-k-1]+val[i]) #include<bits/stdc++.h> using namespace std; const int N=305; int n,m,bigson[N],dp[N][N]; struct node { int val,lson,rson; }tree[N*4]; int dfs(int now,int point) { if(!now||!point) return 0; if(dp[now][point]) return dp[now][point]; dp[now][point]=dfs(tree[now].rson,point); for(int k=0;k<point;k++) { dp[now][point]=max(dp[now][point],dfs(tree[now].lson,k)+dfs(tree[now].rson,point-k-1)+tree[now].val); } return dp[now][point]; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; for(int i=1;i<=n;i++) { int k,s; //爸爸 权值 cin>>k>>s; tree[i].val=s; if(bigson[k]==0) tree[k].lson=i; //如果k还没有其他儿子 那么i就是儿子了 else tree[bigson[k]].rson=i; bigson[k]=i; } cout<<dfs(tree[0].lson,m); return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9391578.html
相关资源：DirectX修复工具V4.0增强版