多叉树转二叉树+树形dp（codevs 1746 贪吃的九头龙 2002noi）

74 阅读 0 评论 49 点赞

我是靠谱客的博主传统保温杯，最近开发中收集的这篇文章主要介绍多叉树转二叉树+树形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 129312910
using 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<<"-1n";
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;
}