前置：树上背包
问题描述：给出一组物品，每个物品有体积v和价值w，其依赖关系形成一棵树，选择一个子节点就要选择其所有祖先节点。给定背包容量，求最大价值。
原始做法：设dp[i][j]为以物品i为子树根结点，在子树内选择j个物品的最大价值。转移：
dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[child][k]);
优化：树上背包的上下界优化
题意：给出一组商品，每件商品原价c[i]，有优惠券可降价d[i]元。优惠券之间有依赖关系，形成一棵树。现在你有b元，求最多买几件商品。
解：设dp[i][j][0/1]为以物品i为子树根结点，在子树内选择j个物品，且物品i用/不用优惠券最多买几个物品。转移方程比较显然，当前不用优惠券所有子节点肯定也不能用优惠券。但不选当前结点可以选子节点，所以转移枚举k的时候可以让j=k。
代码：
#include <bits/stdc++.h> using namespace std; #define maxx 5005 #define maxn 25 #define maxm 205 #define ll long long #define inf 1000000009 #define mod 2520 struct edge{ int u,v,w,next; }e[maxx*2]; int head[maxx]={0},cnt=0; void add(int u,int v){ e[++cnt].u=u;e[cnt].v=v;e[cnt].next=head[u];head[u]=cnt; } ll n,b; ll c[maxx]={0},d[maxx]={0}; ll son[maxx]={0}; ll dp[maxx][maxx][2]={0}; void dfs1(int now){ dp[now][0][0]=0; dp[now][1][0]=c[now]; dp[now][1][1]=d[now]; son[now]=1; for(int i=head[now];i;i=e[i].next){ int to=e[i].v; dfs1(to); for(int j=min(n,son[now]+son[to]);j>=1;j--){ for(int k=max(1ll,j-son[now]);k<=son[to]&&k<=j;k++){ //dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[to][k]); dp[now][j][0]=min(dp[now][j][0],dp[now][j-k][0]+dp[to][k][0]); dp[now][j][1]=min(dp[now][j][1],dp[now][j-k][1]+dp[to][k][0]); dp[now][j][1]=min(dp[now][j][1],dp[now][j-k][1]+dp[to][k][1]); } } son[now]+=son[to]; } } signed main() { scanf("%lld%lld",&n,&b); scanf("%lld%lld",&c[1],&d[1]); for(int i=2;i<=n;i++){ ll x; scanf("%lld%lld%lld",&c[i],&d[i],&x); add(x,i); } for(int i=1;i<=n;i++){ d[i]=c[i]-d[i]; } memset(dp,0x3f3f3f3f,sizeof dp); dfs1(1); ll ans=0; for(int i=0;i<=n;i++){ if(dp[1][i][0]<=b||dp[1][i][1]<=b){ ans=i; } } printf("%lld\n",ans); return 0; } //dp[i][j][k] to node i, choose j goods, using or not the discount
View Code
真っ白な世界で目を覚ませば 在全白的世界中醒来
伸ばす腕は何もつかめない 伸出手却什么也掌握不到
见上げた空が近くなるほどに 仰望天空，似乎有变近的感觉
仆は何を失った？ 我失去了什么吗？透通る波 澄澈纯粹的波纹
映る仆らの影は苍く远く 映照出的我们的影子是那么苍蓝那么遥远
あの日仆は世界を知り 那一天我明白了什么是世界—— 歌に形はないけれど（虽然歌声无形）
原文地址：http://www.cnblogs.com/capterlliar/p/16890545.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
