首页 > 代码库 > POJ 1155

POJ 1155

2024-07-08 22:19:52   222人阅读

很久以前做的树形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\n",i);69             break;70         }71     }72     return 0;73 }
View Code

 


联系
我们