题意:有一个军队n个人要占领m个城市,每个城市有cap的驻扎兵力和val的珠宝,而且这m个城市的占领先后具有依赖关系,军队的每个人可以打败20个城市的防守者,而且占领城市后可以得到城市的珠宝,问最多可以得到多少珠宝?
分类:树形dp入门题,依赖背包
分析:是hdoj1561题目的复杂版,同样我们要构建一颗dp树,从叶子到根往上dp。
定义状态:dp【i】【j】 以节点 i 为根节点的子树,花费 j 的兵力可以得到的最大珠宝数。
状态转移方程:dp【father】【j】 = Max(dp【father】【j】,dp【father】【k】+dp【child】【j-k】)
注意:1:在一个节点即使只有没有兵力,也至少花费1的兵力攻占。
2:注意初始化
代码:
#include <iostream> #include <vector> #include <cstring> #include <cstdio> #include <string> #include <algorithm> #include <vector> #define Del(a,b) memset(a,b,sizeof(a)) const int N = 150; using namespace std; int n,m; int dp[N][N],vis[N]; //dp[i][j]表示在节点i,从以i为根节点的子树下选择j个城市的最大价值 int cap[N],val[N]; vector<int> v[N]; void creat(int o) { vis[o]=1; int tmp=(cap[o]+19)/20; if(tmp>m) return ; for(int i=tmp; i<=m; i++) dp[o][i]=val[o]; for(int i=0; i<v[o].size(); i++) { int t=v[o][i]; if(vis[t]==1) continue; if(v[t].size()>0) { creat(t); for(int j = m ; j > tmp ; j--) //j>1表示此节点一定要取 0-1背包 { for(int k=0; k<=j-tmp; k++) //枚举给当前节点的其他子树留多少可选择的城市 dp[o][j]=max(dp[o][j],dp[o][j-k]+dp[t][k]); } } } if(dp[o][0]>0)//以u为根节点的子树至少要有一个人才可以获得该节点的brain { dp[o][1]=max(dp[o][1],dp[o][0]); dp[o][0]=0; } } int main() { while(cin >> n >> m ) { if(n==-1 && m==-1) break; Del(dp,0); Del(vis,0); for(int i=1; i<=n; i++) scanf("%d%d",&cap[i],&val[i]); for(int i=1; i<n; i++) { int x,y; scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } creat(1); for(int i = 0 ; i <= n ; i ++) v[i].clear(); cout << dp[1][m] << endl; } return 0; }