树形动态规划
树形动态规划
树形动态规划，是指当动态规划的各阶段形成一棵树，利用各阶段之间的关系（动态转移方程），从叶节点（边界）开始逐步向上一层的节点（即父节点）进行动态规划，直到动规到根节点，（即原问题），求的问题的最优解．
典型例题：没有上司的晚会等
没有上司的晚会
【问题描述】
有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。
已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。
【输入：】
第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个部分，一个是建树，另一个就是动态规划，一个好的数据结构，能使你编程非常容易，这也是树形动态规划的难点之一