直接放例题吧：

codevs1380：没有上司的舞会

题意：
某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人（多少人）来能使得晚会的总活跃指数最大。

思路：
任何一个点的取舍可以看作一种决策，那么状态就是在某个点取的时候或者不取的时候，以他为根的子树能有的最大活跃总值。分别可以用f[i,1]和f[i,0]表示第i个人来和不来。

当i来的时候，dp[i][1] += dp[j][0];//j为i的下属
当i不来的时候，dp[i][0] +=max(dp[j][1],dp[j][0]);//j为i的下属

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=6010;
int root,fa[N],n,f[N][2]={0};
bool use[N];
void dp(int x)
{
int i,u;
use[x]=false;
for(i=1;i<=n;++i){
if(use[i]&&fa[i]==x){
dp(i);
f[x][0]+=max(f[i][0],f[i][1]);
f[x][1]+=f[i][0];
}
}
}
int main()
{
int x,y,i,j;
scanf("%d",&n);
memset(use,1,sizeof(use));
for(i=1;i<=n;++i)
scanf("%d",&f[i][1]);
for(i=1;i<=n;++i){
scanf("%d%d",&x,&y);
if(i==n) break;
fa[x]=y;
}
for(i=1;i<=n;++i){
if(!fa[i]){
root=i;
break;
}
}
dp(root);
printf("%dn",max(f[root][0],f[root][1]));
}

cogs1186访问艺术馆

【问题描述】
经过数月的精心准备，Peer Brelstet，一个出了名的盗画者，准备开始他的下一个行动。艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。Peer知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。由于经验老到，他拿下一幅画需要5秒的时间。你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。

【输入】
第1行是警察赶到的时间，以s为单位。第2行描述了艺术馆的结构，是一串非负整数，成对地出现：每一对的第一个数是走过一条走廊的时间，第2个数是它末端的藏画数量；如果第2个数是0，那么说明这条走廊分叉为两条另外的走廊。数据按照深度优先的次序给出，请看样例。
一个展室最多有20幅画。通过每个走廊的时间不超过20s。艺术馆最多有100个展室。警察赶到的时间在10min以内。
【输出】
输出偷到的画的数量。
【样例】
gallery.in gallery.out
60 2
7 0 8 0 3 1 14 2 10 0 12 4 6 2

题解：先用递归建树，保存一下父节点，儿子节点，到父亲的距离，自己末端的画数（有的变量可能用不到）。然后开始树状dp，f[i][j]表示第i个节点取j幅画，然后对左右子树进行选择。一点点的算出来。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=500;
struct S{
int l,r,fa,va,len;
}tr[N];
int s,n=0,f[N][N],num[N]={0};
void in(int i)
{
int x,y,t;
scanf("%d%d",&x,&y);
n+=1;t=n;
if(tr[i].l==0) tr[i].l=n;
else tr[i].r=n;
tr[n].fa=i;
tr[n].len=x*2;
if(y) tr[t].va=y;
else{
in(t);in(t);
}
}
void dp(int x)
{
int i,j;
if(tr[x].l==0){
num[x]=tr[x].va;
for(i=1;i<=tr[x].va;++i)
f[x][i]=5*i;
return ;
}
dp(tr[x].l);
if(x) dp(tr[x].r);
f[x][0]=0;
for(i=0;i<=num[tr[x].l];++i){
for(j=0;j<=num[tr[x].r];++j){
if(i==0) f[x][j]=min(f[x][j],f[tr[x].r][j]+tr[tr[x].r].len);
else if(j==0) f[x][i]=min(f[x][i],f[tr[x].l][i]+tr[tr[x].l].len);
else f[x][i+j]=min(f[x][i+j],f[tr[x].l][i]+tr[tr[x].l].len+f[tr[x].r][j]+tr[tr[x].r].len);
}
}
num[x]=num[tr[x].l]+num[tr[x].r];
}
int main()
{
freopen("gallery.in","r",stdin);
freopen("gallery.out","w",stdout);
int i,j,ans=0;
scanf("%d",&s);
memset(f,127/3,sizeof(f));
in(0);
dp(0);
for(i=0;i<=num[0];++i)
if(f[0][i]<s)
ans=max(ans,i);
printf("%dn",ans);
}

最后

以上就是标致大白为你收集整理的树形dp学习笔记codevs1380：没有上司的舞会cogs1186访问艺术馆的全部内容，希望文章能够帮你解决树形dp学习笔记codevs1380：没有上司的舞会cogs1186访问艺术馆所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。