首页 > 代码库 > 多叉树转二叉树+树形dp（codevs 1746 贪吃的九头龙 2002noi）
多叉树转二叉树+树形dp（codevs 1746 贪吃的九头龙 2002noi）
题目传送门
看到这个题目我们要先把问题简化了，条件中是多叉树，我们可以把它转换成二叉树，左边是儿子右边是兄弟的储存方式。
首先先判断否的部分，当总的果子小于需求，也就是N-k<M-1时输出-1。
我们再判断是的部分
如果没有大头，一定存在难受值为0的方案但是现在题目中有大头，我们就可以按按照小头的个数进行分类
1.有一个小头，我们要考虑小头和大头的难受值之和。
2.有多个小头，因为小头可以在奇偶的进行变换，所以我们只需要考虑大头的难受值。
分析到这里，我们就可以发现是树形dp我们设f[i][j][k]表示以i为根的子树，大头吃j个果子，他父亲节点为k，k=1是大头吃的,k=0是小头吃的。
下面分析的部分摘自kiana810的博客：
f[i][j][k]=min(f1[i][j][k],f2[i][j][k])
1）f1[i][j][k]=f[son][j1][1]+f[brother][j-j1-1][k]+d(k,1)*cost(i,fa[i]);(j1<j)
2）f2[i][j][k]=f[son][j1][0]+f[brother][j-j1][k]+d(k,0)*cost(i,fa[i]);(j1≤j)
其中son，brother分别表示i的左儿子和右兄弟（对应二叉树左右子树），j1是枚举的变量，cost是i到fa[i]的树枝难受值。d的定义如下：
1）若i=1且j=1，则大头吃下了相连的果子，需要付出难受值，返回1；
2）若i=0且j=0，但Ｍ=2，只有一个小头，小头吃下了相连的果子，需要付出难受值，返回1；
3）其它情况，总有办法分配果子使得九头龙不付出难受值，返回0。
思考完之后，我们不要忘记考虑边界 f[0][0][k]=0,f[0][j][k]=inf这很好理解，我们假设有一个虚拟节点，他是二叉树根节点的根节点。
分析完之后，放上代码吧，写完之后我感觉有些疲倦，兴许是我太菜了呢~
#include<bits/stdc++.h>#define inf 129312910using namespace std;int N,M,K,root;vector<int> g[400];//存权值 vector<int> p[400];//存子节点 int f[400][400][2];int fa[400];struct Point{ int l,r,c;//分别为左儿子，右儿子，和儿子到父亲的权值 Point(){l=r=c=0;}}t[400];void build(int x){ if(p[x].empty()) return ; t[x].l=p[x][0];t[p[x][0]].c=g[x][0]; for(int i=1;i<p[x].size();i++) { t[p[x][i-1]].r=p[x][i];//只找儿子节点，并且一次在后插入 t[p[x][i]].c=g[x][i]; } for(int i=0;i<p[x].size();i++) build(p[x][i]);}int d(int x,int y){ return (( x==0&&y==0&&M==2)||(x&&y));}int dp(int i,int j,int k)//递归dp的过程{ if(f[i][j][k]==-1)//如果之前没有搜索过 { int v,u=inf; for(int a=0;a<=j;a++) { v=dp(t[i].l,a,0)+dp(t[i].r,j-a,k)+d(k,0)*t[i].c; u=min(u,v); if(a<j)//防止越界important!!! v=dp(t[i].l,a,1)+dp(t[i].r,j-a-1,k)+d(k,1)*t[i].c; u=min(u,v); } f[i][j][k]=u; } return f[i][j][k];}int main(){ cin>>N>>M>>K; if(N-K<M-1)//判断有无解 { cout<<"-1\n"; return 0; } int t1,t2,t3; int ans=0; for(int i=1;i<N;i++) { cin>>t1>>t2>>t3; p[t1].push_back(t2); g[t1].push_back(t3); fa[t2]=t1; } for(int i=1;i<=N;i++) if(!fa[i]) { root=i; build(i); break; } memset(f,-1,sizeof(f));//初始化为-1，也算是没有遍历过 f[0][0][1]=f[0][0][0]=0; for(int i=1;i<=K;i++) f[0][i][0]=f[0][i][1]=inf; ans=dp(t[root].l,K-1,1);//从根节点的第一个节点，也就是在二叉树中的左儿子 cout<<ans<<endl; return 0;}
多叉树转二叉树+树形dp（codevs 1746 贪吃的九头龙 2002noi）