HDU4276 The Ghost Blows Light（树形DP+背包）

题目大概说一棵n个结点树，每个结点都有宝藏，走过每条边要花一定的时间，现在要在t时间内从结点1出发走到结点n，问能获得最多的宝藏是多少。

放了几天的题，今天拿出来集中精力去想，还是想出来了。

首先，树上任意两点间最短的那条路径是唯一的，且不管怎么走一定都会走过那条路径上的所有点，也就是说整个行程可以看成两部分组成：一部分就是1到n的最短路径，另一部分就是从这个路径上的某点出发绕回该点的路径。

这样问题就清晰了，现在关键在求第二部分：

先用树上背包求出：dp[u][t]，表示从在以u点为根的子树中从u点出发且不经过n结点及其祖先结点最后回到u点总共用时t能获得最多的宝藏
最后从1到n最短的那条路径上的各个点u看作物品，有t种规格的体积，每种体积价值是dp[u][t]，背包容量为总时间-走那条最短路所需时间，这样再做一次背包，求出装满某体积（用某时间）能得到的最大价值就OK了。
注意的是那个状态是不经过n结点及其祖先结点，这是为了不重复统计，1到n路径上的点本身就是父子关系。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define MAXN 111

 struct Edge{

     int v,w,next;

 }edge[MAXN<<];

 int NE,head[MAXN];

 void addEdge(int u,int v,int w){

     edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];

     head[u]=NE++;

 }

 int n,t,val[MAXN],d[MAXN][],par[MAXN],weight[MAXN];

 bool dp(int u){

     bool flag=;

     d[u][]=val[u];

     for(int i=head[u]; i!=-; i=edge[i].next){

         int v=edge[i].v;

         if(v==par[u]) continue;

         par[v]=u;

         weight[v]=edge[i].w;

         if(dp(v)){

             flag=;

             continue;

         }

         for(int j=t; j>=; --j){

             for(int k=; ; ++k){

                 if(edge[i].w*+k>j) break;

                 if(d[v][k]==- || d[u][j-edge[i].w*-k]==-) continue;

                 d[u][j]=max(d[u][j],d[u][j-edge[i].w*-k]+d[v][k]);

             }

         }

     }

     if(u==n) return ;

     return flag;

 }

 int rec[MAXN],rn,tot;

 void dfs(int u){

     if(u!=){

         tot+=weight[u];

         dfs(par[u]);

     }

     rec[rn++]=u;

 }

 int ans[MAXN][];

 int main(){

     int a,b,c;

     while(~scanf("%d%d",&n,&t)){

         NE=;

         memset(head,-,sizeof(head));

         for(int i=; i<n; ++i){

             scanf("%d%d%d",&a,&b,&c);

             addEdge(a,b,c);

             addEdge(b,a,c);

         }

         for(int i=; i<=n; ++i) scanf("%d",val+i);

         memset(d,-,sizeof(d));

         dp();

         rn=tot=;

         dfs(n);

         tot=t-tot;

         memset(ans,-,sizeof(ans));

         for(int i=; i<=tot; ++i) ans[][i]=d[rec[]][i];

         for(int i=; i<rn; ++i){

             for(int j=; j<=tot; ++j){

                 for(int k=; k<=tot; ++k){

                     if(j+k>tot || ans[i-][j]==- || d[rec[i]][k]==-) continue;

                     ans[i][j+k]=max(ans[i][j+k],ans[i-][j]+d[rec[i]][k]);

                 }

             }

         }

         int res=-;

         for(int i=; i<=tot; ++i) res=max(res,ans[rn-][i]);

         if(res==-) puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");

         else printf("%d\n",res);

     }

     return ;

 }

巴特西

HDU4276 The Ghost Blows Light（树形DP+背包）

最新文章

热门文章