题目链接http://xcacm.hfut.edu.cn/oj/problem.php?id=1102

题目大意:树上取点。父亲出现了,其儿子包括孙子...都不能出现。给定预算,问最大值。

解题思路

把树形背包的模板改一改。

首先对于叶子结点,直接初始化就行了。这步不可以跳过,因为存在负权,仅仅依靠最后的max是不行的。

对于普通结点,首先不考虑当前根,先把全部预算分给儿子。

即for(int j=W; j>=1; j--)

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

最后再做一次dp[root][cost~m]=max(dp[root][cost~m],w[root])

意思为要么取所有儿子,要么只取根。

#include "cstdio"
#include "iostream"
#include "cstring"
using namespace std;
#define maxn 1200
int c[maxn],w[maxn],dp[maxn][maxn],head[maxn],tol;
int n,W,u;
struct Edge
{
int to,next;
}e[maxn];
void addedge(int u,int v)
{
e[tol].to=v;
e[tol].next=head[u];
head[u]=tol++;
}
void dfs(int root)
{
int i=root,cost=c[root];
if(head[root]==-) for(int i=cost;i<=W;i++) dp[root][i]=w[root];
for(int a=head[root];a!=-;a=e[a].next)
{
int t=e[a].to;
dfs(t);
for(int j=W; j>=; j--)
for(int k=; k<=j; k++)
dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[t][k]);
}
for(int i=cost;i<=W;i++) dp[root][i]=max(dp[root][i],w[root]);
}
int main()
{
//freopen("in.txt","r",stdin);
memset(head,-,sizeof(head));
scanf("%d%d",&n,&W);
for(int i=;i<=n;i++)
{
scanf("%d",&u);
addedge(u,i);
}
for(int i=;i<=n;i++) scanf("%d",&c[i]);
for(int i=;i<=n;i++) scanf("%d",&w[i]);
dfs();
printf("%d\n",dp[][W]); }
2600 2013217098 Accepted
7176
56
C++/Edit 1188 B 2014-10-20 20:18:43

最新文章

  1. 获取IP地址 &amp; 伪装IP地址发送请求
  2. 【BZOJ-3156】防御准备 DP + 斜率优化
  3. [zz] 英文大写缩写前要加THE吗
  4. MySQL页面打捞工具使用方法
  5. HTML -- 元素和属性
  6. 从tcp原理角度理解Broken pipe和Connection reset by peer的区别
  7. XCode 7上传遇到ERROR ITMS-90535 Unexpected CFBundleExecutable Key. 的解决办法(转)
  8. jquery效果,多个div,点击任何一个div,那么这个div会切换文字,变换背景颜色,再次点击其他的div ,这个div会发生刚才的变化,之前点击的div的颜色会变回来
  9. 图文详解如何快捷搭建LNMP服务环境
  10. Chrome浏览器扩展开发系列之九:Chrome浏览器的chrome.alarms.* API
  11. Metasploit渗透测试梗概
  12. Jenkins-job之间依赖关系配置
  13. Django models字段查询谓词表
  14. 【HTTPS】自签CA证书 &amp;&amp; nginx配置https服务
  15. jexus手动跨域设置
  16. Windows bat 学习(高级)
  17. (3.4)mysql基础深入——mysql.server启动脚本源码阅读与分析
  18. C语言 fread()与fwrite()函数说明与示例
  19. 如何将M文件转成独立可执行程序
  20. Node.js:模块系统、函数

热门文章

  1. 【分布式存储】GlusterFS failing to mount at boot with Ubuntu 14.04
  2. 【SpringMVC】SpringMVC系列2之@RequestMapping 映射约束请求
  3. spring中context:property-placeholder/元素
  4. poj 1328
  5. 如何给spine骨骼动画挂载粒子特效
  6. iOS 和 Android 中的Alert
  7. centos 单独安装PHP的mysql和mysqli扩展
  8. Linux系统排查1——内存篇
  9. PHP--TP框架----把查询到的数据,显示在模型(模板)里面
  10. 【学习笔记】移动Web手册(PPK力作)