树形动态规划

树形动态规划，是指当动态规划的各阶段形成一棵树，利用各阶段之间的关系（动态转移方程），从叶节点（边界）开始逐步向上一层的节点（即父节点）进行动态规划，直到动规到根节点，（即原问题），求的问题的最优解．

典型例题：没有上司的晚会等

没有上司的晚会

【问题描述】

有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。

已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。

【输入：】

第1行一个整数N（1<=N<=6000）表示公司的人数。

接下来N行每行一个整数。第i行的书表示第i个人的气氛值x（-128<=x<=127）。

接下来每行两个整数L，K。表示第K个人是第L个人的上司。

输入以0 0结束。

【输出】：

一个数，最大的气氛值和。

【样例输入】

7

1

1

1

1

1

1

1

1 3

2 3

6 4

7 4

4 5

3 5

0 0

【样例输出】

5

【分析】

如上例，上司与小兵之间的关系构成一棵树。

5

| \\

3 4

| \\ | \\

1 2 6 7

又是求最优解，并且每一个节点的取舍关乎到全局 因此，此题可用树形动态规划

我们可用f[v][0]存储不选编号为V的节点的最优解，f[v][1]存储选编号为V的节点的最优解

#include<iostream>

using namespace std;

int main(){

int n,qf[201],f[201][2],shs[201],xb[201][201],shu[201][201],x,s,maxc,j,k,a,b,l,i;//qf存储每个人的气氛值，shs存储每个人的上司，xb存储没个人的下属，shu存储构成的树

cin>>n;

for(i=0;i<=n;i++){xb[i][0]=0;shs[i]=0;}

for(i=1;i<=n;i++)cin>>qf[i];l=1;k=1;

while(l!=0 || k!=0){

cin>>l>>k;

shs[l]=k;

xb[k][0]++;

xb[k][xb[k][0]]=l;

}

maxc=0;

for(i=1;i<=n;i++)

{

x=i;s=1;

while(shs[x]!=0){x=shs[x];s=s+1;}

shu[s][0]++;

shu[s][shu[s][0]]=i;

if (s>maxc)maxc=s;

}//建树,maxc存储最大层数

for(i=maxc;i>=1;i--)

for(j=1;j<=shu[i][0];j++)

{

if(xb[shu[i][j]][0]==0){

f[shu[i][j]][0]=0;f[shu[i][j]][1]=qf[shu[i][j]];

}

else

{

f[shu[i][j]][0]=0;f[shu[i][j]][1]=qf[shu[i][j]];

for(k=1;k<=xb[shu[i][j]][0];k++){

a=f[xb[shu[i][j]][k]][0];b=f[xb[shu[i][j]][k]][1];

f[shu[i][j]][1]+=a;

if(b>a)a=b;

f[shu[i][j]][0]+=a;

}//动态转移方程

}

}s=0;

for(i=1;i<=shu[1][0];i++){

a=f[shu[1][i]][0];b=f[shu[1][i]][1];

if(a<b)a=b;

s=s+a;

}//从顶头上司那里择优选择

cout<<s<<endl;

system("pause");

return 0;

}

大家看到，树形动态规划基本上可以分为2个部分，一个是建树，另一个就是动态规划，一个好的数据结构，能使你编程非常容易，这也是树形动态规划的难点之一