hdu 4340 树形DP - c++编程基础

题意：一棵树，每个节点可以染两种颜色，每种颜色都有一定的代价，有一个特殊的地方就是如果相邻点已经被染了相同的颜色，当前点染这种颜色的时候只需要一半的代价
最后问：将整棵树都染色最少需要多大代价。

DP的时候要先想好怎么去利用限制条件将状态描述好，因为跟一个点相邻的点中如果有一个点被染成相同颜色且用了全部代价，那么这个点染这种颜色只需要一半的代价了，所以，我们可以设计这样的状态，
F[u][0] : 对u染第一种颜色的时候还没有选定染全色的节点
F[u][1]: 对u染第一种颜色，已经选定了染全色的节点
g[u][0],g[u][1]就是第二种颜色，状态类似
在转移的时候，我们可以将子节点所有的已求好的状态都列出来
比如要求f[u][0]
子节点的状态 f[v][0],f[v][1],g[v][0],g[v][1] 均已经求好
则可得： f[u][0]+=min(g[v][1],f[v][0]) ,因为f[u][0]表示u染第一种颜色的时候还没有确定跟u相连的点中那个点染全色，所以不能从f[v][1]这个已经确定的状态转移过来
在求f[u][1]的时候，要么我们对u节点染全色，要么在u的某个子树中染全色，所以f[u][1]=f[u][0]+min(a[u],ma);
其中 ma表示f[v][1]-min(g[v][1],f[v][0])的最小值，因为要挑选一棵子树的f[v][1]状态来替换原来加进来的状态
最后f[u][0]在加上a[u]/2即可；
最后注意，如果是叶子节点要特判一下，叶子节点没有子树节点。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int inf = 100000;
const int maxn = 101;
vector edge[maxn];
int a[maxn],b[maxn];
int f[maxn][2],g[maxn][2];
void dfs(int u,int fa)
{
f[u][0]=0;
g[u][0]=0;
int sz=edge[u].size();
int m1=inf,m2=inf;
bool leaf=true;
for(int i=0;i {
int v=edge[u][i];
if(v==fa) continue;
dfs(v,u);
leaf=false;
int tmp=min(f[v][0],g[v][1]);
f[u][0]+=tmp;
m1=min(m1,f[v][1]-tmp);

tmp=min(g[v][0],f[v][1]);
g[u][0]+=tmp;
m2=min(m2,g[v][1]-tmp);
}
if(leaf)
{
f[u][1]=a[u];
f[u][0]=a[u]/2;

g[u][1]=b[u];
g[u][0]=b[u]/2;

}
else
{
//printf("m1=%d\n",m1);
//printf("f[u][0]=%d\n",f[u][0]);

f[u][1]=f[u][0] + min(a[u],m1+a[u]/2);
f[u][0]+=a[u]/2;

//printf("%d %d\n\n",f[u][0],f[u][1]);

g[u][1]=g[u][0] + min(b[u],m2+b[u]/2);
g[u][0]+=b[u]/2;

//printf("u=%d bu=%d %d %d\n",u,b[u],g[u][0],g[u][1]);
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<=n;i++) edge[i].clear();
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1,u,v;i {
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1,0);
printf("%d\n",min(f[1][1],g[1][1]));
}
return 0;
}

作者：haha593572013