hdoj4276（树形dp+分组背包）

题目链接：https://vjudge.net/problem/HDU-4276

题意：给出一棵树，起点为1，时间为V，终点为n，每个点有一个价值a[u]，每条边有一个时间花费w，求在时间V内到达终点n可以获得的最大价值。

思路：

　　考虑边有两种情况，一种是属于1->n路径上的（只用走一次），一种是不属于该路径上的（需要走两次），为了统一，不妨把V减去1-n路径上的权值和，然后把1->n路径上边的权值置为0。

　　此时就转换为求在起点1，在时间V内回到起点的最大价值。用dp[u][j]表示在点u有时间j，最后回到点u的最大价值，dp[u][j]初始化为a[u]（0<=j<=V），转移方程为：
　　　　dp[u][j]=max(dp[u][j],dp[u][j-tmp-k]+dp[v][k]。

　　其中v为u的子结点，tmp=2×w(u,v)。

AC代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int n,V,a[],e[][],dp1[],dp2[][];

void dfs1(int u,int fa){

    dp1[u]=-;

    if(u==n) dp1[u]=;

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

        if(e[u][i]!=-){

            if(i==fa) continue;

            dfs1(i,u);

            if(dp1[i]!=-){

                dp1[u]=dp1[i]+e[u][i];

                e[u][i]=e[i][u]=;

            }

        }

}

void dfs2(int u,int fa){

    for(int j=;j<=V;++j)

        dp2[u][j]=a[u];

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

        if(e[u][i]!=-){

            if(i==fa) continue;

            dfs2(i,u);

            int tmp=*e[u][i];

            for(int j=V;j>=tmp;--j)

                for(int k=;k<=j-tmp;++k)

                    dp2[u][j]=max(dp2[u][j],dp2[u][j-tmp-k]+dp2[i][k]);

        }

}

int main(){

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

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

            for(int j=;j<=n;++j)

                e[i][j]=-;

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

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            e[u][v]=e[v][u]=w;

        }

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

            scanf("%d",&a[i]);

        dfs1(,);

        if(V<dp1[]){

            printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");

            continue;

        }

        V-=dp1[];

        dfs2(,);

        printf("%d\n",dp2[][V]);

    }

    return ;

}

巴特西

hdoj4276（树形dp+分组背包）

最新文章

热门文章