没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm

树形dp背包 对任一节点，取得最大值相当于在确定根节点消耗之后对所有子树进行01背包，获得1~m每个状态的最大值，然后向上递归，直至找到根节点，此时求得的最大值即为所求 状态转移方程：dp[i][t]=max(dp[i][t],dp[i][k]+dp[son[i]][t-k])(k=0,1,2......) #include <iostream>using namespace std;i

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

链接：点击打开链接 题意：有n个节点组成一棵树,有m个士兵,必须从1号房间开始攻打,每个洞防御值1价值b,一个士兵只能产生20的伤害,为了拿到这个节点的价值,必须留下一些士兵消灭这个洞的防御值(并且留下的士兵不可以再去攻打其他节点，并且必须攻打了父节点才可以攻打子节点),问这m个士兵可以得到的最大价值是多少 代码： #include <math.h>#include <vector>#i