【HDU1011】Starship Troopers

题目大意：给定一棵 N 个节点的无根树，每个节点有一个重量和一个价值，现给出一些单位，每个单位可以接受 20 个重量单位，求如何分配这些单位，使得获得的价值最大。

题解：dp 好题qwq。。真的毒瘤。

状态转移很好设计，$dp[i][j]$ 表示以 i 为根节点的子树中，分配 j 个单位可以获得的最大价值是多少，转化成分组背包。

需要注意的点如下：

对于公式$$\lfloor {n+m-1\over m} \rfloor$$与公式$$\lfloor {n-1\over m} \rfloor+1$$并不是完全等价的，对于 n 为 0 的时候，只有第一个公式是对的。
对于 dp 过程中，当前节点价值的计入不能仅仅更新单个dp值，应整体更新所有可以更新的值，最好将更新子树根节点的操作放在递归最后进行。

代码如下

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int maxn=110;

vector<int> G[maxn];

int n,m,bug[maxn],brain[maxn],dp[maxn][maxn];

void dfs(int u,int fa){

    int num=(bug[u]+19)/20;

    for(auto v:G[u]){

        if(v==fa)continue;

        dfs(v,u);

        for(int j=m;j>=num;j--)

            for(int k=1;k<=j-num;k++)

                dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);

    }

    for(int i=num;i<=m;i++)dp[u][i]+=brain[u];

}

void read_and_parse(){

    for(int i=1;i<=n;i++)scanf("%d%d",&bug[i],&brain[i]);

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

        int x,y;

        scanf("%d%d",&x,&y);

        G[x].pb(y),G[y].pb(x);

    }

}

void solve(){

    if(!m)return (void)puts("0");

    dfs(1,0);

    printf("%d\n",dp[1][m]);

}

void init(){

    memset(dp,0,sizeof(dp));

    for(int i=1;i<=n;i++)G[i].clear();

}

int main(){

    while(scanf("%d%d",&n,&m)&&n!=-1&&m!=-1){

        init();

        read_and_parse();

        solve();

    }

    return 0;

}

巴特西

【HDU1011】Starship Troopers

最新文章

热门文章