题目:hdoj1561The more,The Better
题意:ACboy很喜欢玩一种战略游戏,在一个地图上,有N座城堡,每座城堡都有一定的宝物,在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因,有些城堡不能直接攻克,要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗?
分析:
分类:树形dp入门,依赖背包
做这题前又看了一遍背包9讲,感觉太经典了,尤其是泛化背包,简直是精华。这题的关系就是裸地依赖背包,用树形dp解。
首先,限制条件是选择m个物品,而每个物品最多选一次,跟0-1背包的区别在于有依赖关系,那么这层依赖关系我们可以借助于一个树来解决。借助dfs,从根节点开始dfs,然后直到叶子节点,回朔的时候进行0-1背包dp。
定义状态:dp [ i ] [ j ] 表示在节点i,从以i为根节点的子树下选择j个城市的最大价值
初始化:dp [ i ] [ j ] =val [ i ](i节点的价值)(1 < = j < = m)
转移方程 dp【father】【j】 = max (dp【father】【j】,dp【father】【k】+dp【child】【j-k】);由前面的dfs可见,我们是用子节点更新父节点,用j枚举父节点选择的城市数,k枚举留给其他子节点选择城市数,那么就可以转移了
注意:此题出给很多初始节点,也就是有很多森林,我们要设置一个超级root连接子树的根节点即可。
代码:
#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) { for(int i=0; i<v[o].size(); i++) { int t=v[o][i]; if(vis[t] == 0 && v[t].size()>0) creat(t); for(int j = m ; j > 1 ; j--) //j>1表示此节点一定要取 0-1背包 { for(int k=1; k<j; k++) //枚举给当前节点的其他子树留多少可选择的城市 dp[o][j]=max(dp[o][j],dp[o][k]+dp[t][j-k]); } } } int main(){ while(cin >> n >> m,n&&m){ m ++; // 加一个根节点 Del(dp,0); for(int i = 1 ; i <= n ; i ++){ int a,b; cin >> a >> b; v[a].push_back(i); for(int j = 1 ; j <= m ; j++) dp[i][j] = b; // 初始化时,每个节点,所有状态都是拿自己一个 } creat(0); for(int i = 0 ; i <= n ; i ++) v[i].clear(); cout << dp[0][m] << endl; } return 0; }