首页 > 代码库 > URAL_1018 Binary Apple Tree 树形DP+背包

URAL_1018 Binary Apple Tree 树形DP+背包

2024-07-08 03:47:23   220人阅读

这个题目给定一棵树，以及树的每个树枝的苹果数量，要求在保留K个树枝的情况下最多能保留多少个苹果

一看就觉得是个树形DP，然后想出 dp[i][j]来表示第i个节点保留j个树枝的最大苹果数，但是在树形过程中，有点难表示转移

后来看了下大神的做法才知道其实可以用背包来模拟 树枝的去留，其实真的是个背包诶，每个子树枝就相当于物品，他占用了多少树枝量，带来多少的收益，就是用背包嘛，于是用树形DP+背包就可以做了

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define N 210using namespace std;int u[N],v[N],e[N],nt[N],ft[N];int dp[N][N];int cnt;void add(int a,int b,int val){    u[cnt]=a;    v[cnt]=b;    e[cnt]=val;    nt[cnt]=ft[a];    ft[a]=cnt++;}int n,k;int sum[N];void dfs(int x,int f){    sum[x]=1;    for (int i=ft[x];i>=0;i=nt[i]){        int nx=v[i];        if (nx==f) continue;        dfs(nx,x);        sum[x]+=sum[nx];        for (int j=sum[x];j>=1;j--){            for (int w=1;w<=sum[nx] && w<j;w++){                dp[x][j]=max(dp[x][j],dp[x][j-w]+dp[nx][w]+e[i]);            }        }    }}int main(){    while (scanf("%d%d",&n,&k)!=EOF)    {        cnt=0;        int a,b,c;        memset(ft,-1,sizeof ft);        for (int i=1;i<n;i++){            scanf("%d%d%d",&a,&b,&c);            add(a,b,c);            add(b,a,c);        }        memset(dp,0,sizeof dp);        dfs(1,-1);        printf("%d\n",dp[1][k+1]);    }    return 0;}

 


联系
我们