题目：         链接：点击打开链接 题意：         n个房间组成一棵树，你有m个战队，从1号房间开始依次clear每个房间，在每个房间需要花费的战队个数是bugs/20，得到的价值是the possibility of capturing a brain，求最大的价值。 算法：        树形dp，有依赖的背包问题。（依次clear每个房间） 思路：

/*题意：星河战队要去完成任务：用有限的战士去俘获尽可能多的首脑。条件和注意：1：一颗树（没有重边，没有环，没有孤立点），表示敌军的基地地图2：一个战士可以战胜20个敌人，保证战士不重复战斗，不走回路。3：要想抓到首脑，必须要有战士进入房间。分析：树上跑背包。*/#include<iostream>#include<cstring>#include<algorithm>#inc

这道题是一个树形 背包问题，或者说树形DP问题，房间的管道形成树。 背包问题的特点： 最优子结构，可分解， 解决办法： 常见的有递归（自顶向下），搜索（自底向上），背包注意的问题，为什么要自底向上搜索？？？？ 需要好好学习背包问题； #include <iostream>#include<vector>#include<cstdio>#include<cstring>using n

人一我百，人十我万！！ 树形DP加上一些背包的思想，有一些模板的感觉。 ac code： #include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <cmath>#include <vector>#include <list>

1、http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1111 2、题目大意： 题意是说有n个洞形成一棵树，你有m个士兵，每个洞都有一定数量的虫子和一定概率的首脑。每个士兵可以攻击20只虫子。而且想要攻击下面的洞的虫子，必须要攻击上层的虫子，问你花费这m个士兵，最多可以得到多少概率的首脑。 定义dp[x][y]表示在x结点

题目很水，但是有很多易错点。。。 注意： 1，题目输入的时候是自由树，无向边。 2，如果某个点的bugs是0，也必须有至少一个士兵经过此点。 做法:： 按照题意，把自由树转为二叉树。 然后树形dp dp[x][y]:在二叉树中的x节点为根的树中，使用了y个士兵获得的最大值。 dp[x][y]=dp[node[x].l][k]+nval[x]+dp[node[x].r][y-k];