这是自己第一道背包上树形结构问题,不是很理解这个概念的可以先看看背包九讲
自己第一次做,看了一下别人的思路,结合着对简单背包问题的求解方式自己一次AC了还是有点小激动的
题目大意是:
攻克m个城市,每个城市都有对应数量的宝贝,攻克某一个城市必须保证其对应的某一个特定城市已经被攻克,希望得到最多数量的宝贝
很容易根据题目画出一个对应关系的树形结构,每个节点都有一个对应的宝物的数量
我们用dp[i][j]存 i 号节点它下方子树中 有 j 个城市被攻克时得到的宝物最大数量 , 此时的 i 号是没有被攻克的!
然后通过dfs自底向上更新
1 /* 2 总的u下方子树攻克了j个城市,为当前v姿势分配k个城市攻克 3 添加当前v包含了攻克k-1个子树的城市,要添加子树v必须 4 同时保证v被攻克,所以加上的是dp[v][k-1] + val[v] 5 */ 6 for(int j = m ; j>=1 ; j--){ 7 for(int k = j ; k>0 ; k--){ 8 dp[u][j] = max(dp[u][j] , dp[u][j-k] + dp[v][k-1] + val[v]); 9 } 10 }
这里可以理解为当根节点u下方有 j 个城市被攻克时, 若有 k 个城市的攻克来自v的子树, 那么v必然要被攻克 , val[v],不然其下方的城市不能攻克
除去v还有 k -1个v节点对应子树中的城市要攻克 ,也就是 dp[v][k-1]
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 const int N = 205; 6 7 int dp[N][N] , val[N] , first[N] , k; 8 9 struct Edge{ 10 int y , next; 11 }e[N]; 12 13 void add_edge(int x , int y) 14 { 15 e[k].y = y , e[k].next = first[x]; 16 first[x] = k++; 17 } 18 19 void dfs(int u , int m) 20 { 21 for(int i=first[u] ; i!=-1 ; i=e[i].next){ 22 int v = e[i].y; 23 dfs(v , m); 24 /* 25 总的u下方子树攻克了j个城市,为当前v姿势分配k个城市攻克 26 添加当前v包含了攻克k-1个子树的城市,要添加子树v必须 27 同时保证v被攻克,所以加上的是dp[v][k-1] + val[v] 28 */ 29 for(int j = m ; j>=1 ; j--){ 30 for(int k = j ; k>0 ; k--){ 31 dp[u][j] = max(dp[u][j] , dp[u][j-k] + dp[v][k-1] + val[v]); 32 } 33 } 34 } 35 } 36 37 int main() 38 { 39 // freopen("a.in" , "r" , stdin); 40 int n , m , a , b; 41 while(scanf("%d%d" , &n , &m) , n||m) 42 { 43 memset(first , -1 , sizeof(first)); 44 k = 0; 45 for(int i=1 ; i<=n ; i++) 46 { 47 scanf("%d%d" , &a , &b); 48 add_edge(a , i); 49 val[i] = b; 50 } 51 memset(dp , 0 , sizeof(dp)); 52 dfs(0 , m); 53 54 printf("%d\n" , dp[0][m]); 55 } 56 return 0; 57 }