首页 > 代码库 > URAL_1018 Binary Apple Tree 树形DP+背包
URAL_1018 Binary Apple Tree 树形DP+背包
这个题目给定一棵树,以及树的每个树枝的苹果数量,要求在保留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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。