POJ 1155

很久以前做的树形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 }

View Code

使用深搜，再运用背包来解决。

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
",i);
69             break;
70         }
71     }
72     return 0;
73 }

View Code