很久以前做的树形DP题，今天再遇到时，竟然不会了，所以写写。。
设数组：
prf[MAX][MAX],cost[MAX],sum[MAX]。分别表示，在第i个结点为根的子树内的情况下，若有j个用户申请看电视，所能得到的最大费用。cost表示传送到i点时所花的费用，而sum表示当前结点为根的子树内已访问的叶子结点的个数（即用户）。
1 void dfs(int v,int fa){ 2 if(T[v].size()>0){ 3 for(int i=0;i<T[v].size();i++){ 4 dfs(T[v][i],v); 5 } 6 } 7 if(T[v].size()==0) 8 sum[v]=1; 9 sum[fa]+=sum[v]; 10 prf[fa][0]=0; 11 for(int i=sum[fa];i>0;i--){ 12 for(int j=sum[v];j>0;j--){ 13 if(prf[fa][i-j]!=-INF&&prf[v][j]!=-INF) 14 prf[fa][i]=max(prf[fa][i],prf[fa][i-j]+prf[v][j]-cost[v]); 15 } 16 } 17 }
使用深搜，再运用背包来解决。
for(int i=sum[fa];i>0;i--){
for(int j=sum[v];j>0;j--){
if(prf[fa][i-j]!=-INF&&prf[v][j]!=-INF)
prf[fa][i]=max(prf[fa][i],prf[fa][i-j]+prf[v][j]-cost[v])
}
}
枚举父结点当前已访问的用户数，再枚举当前结点子树内该问了的用户数，若要在父结点的状态中加入j个当前结点有用户，则
prf[fa][i]=max(prf[fa][i],prf[fa][i-j]+prf[v][j]-cost[v])。这是拿加入j个用户后与当前i个用户的费用的比较。
前提条件时if(prf[fa][i-j]!=-INF&&prf[v][j]!=-INF)，因为要在状态存在的情况下才能进行。
1 #include <iostream> 2 #include <vector> 3 4 const int maxn=3010; 5 const int INF=100000; 6 using namespace std; 7 int n,m; 8 int prf[maxn][maxn]; 9 int cost[maxn]; 10 int sum[maxn]; 11 12 vector<int>T[maxn]; 13 14 void init(){ 15 for(int i=0;i<=n;i++) 16 for(int j=0;j<=m;j++) 17 prf[i][j]=-INF; 18 memset(cost,0,sizeof(cost)); 19 memset(sum,0,sizeof(sum)); 20 for(int i=0;i<=n;i++) 21 T[i].clear(); 22 } 23 int max(int a,int b){ 24 if(a<b) 25 return b; 26 return a; 27 } 28 void dfs(int v,int fa){ 29 if(T[v].size()>0){ 30 for(int i=0;i<T[v].size();i++){ 31 dfs(T[v][i],v); 32 } 33 } 34 if(T[v].size()==0) 35 sum[v]=1; 36 sum[fa]+=sum[v]; 37 prf[fa][0]=0; 38 for(int i=sum[fa];i>0;i--){ 39 for(int j=sum[v];j>0;j--){ 40 if(prf[fa][i-j]!=-INF&&prf[v][j]!=-INF) 41 prf[fa][i]=max(prf[fa][i],prf[fa][i-j]+prf[v][j]-cost[v]); 42 } 43 } 44 } 45 46 int main(){ 47 while(~scanf("%d%d", &n, &m)) 48 { 49 init(); 50 int t=0,c,k,y; 51 T[0].push_back(1); 52 while((++t)<=n-m){ 53 scanf("%d",&k); 54 for(int i=1;i<=k;i++){ 55 scanf("%d%d",&y,&c); 56 T[t].push_back(y); 57 cost[y]=c; 58 } 59 } 60 for(k=n-m+1;k<=n;k++){ 61 scanf("%d",&c); 62 prf[k][1]=c; 63 prf[k][0]=0; 64 } 65 dfs(1,0); 66 for(int i=m;i>=0;i--) 67 if(prf[1][i]>=0){ 68 printf("%d\n",i); 69 break; 70 } 71 } 72 return 0; 73 }
原文：http://www.cnblogs.com/jie-dcai/p/3798327.html
