The more, The Better
树形DP题目。树形DP+多重背包问题。由于初始化的原因,wrong了几次。方程很好写。我们先增加一个额外的节点0,同时将对应的攻克的城堡数目+1.方程如下:dp[r][j] = max(dp[r][j] , dp[r][j-k] + dp[u][k])其中u是r的儿子节点.
#include <iostream> #include <stdio.h> #include <string.h> #include <vector> using namespace std ; const int maxn = 205 ; vector<int> G[maxn] ; int dp[maxn][maxn] ; int w[maxn] ; int n ; int m ; void init(){ for(int i = 0 ; i < maxn ; i ++) G[i].clear() ; memset(dp , 0 , sizeof(dp)) ; } void dfs(int r){ dp[r][1] = w[r] ; for(int i = 0 ; i < G[r].size(); i ++) dfs(G[r][i]) ; for(int i = 0 ; i < G[r].size() ; i ++){ int u = G[r][i] ; for(int j = m ; j > 1 ; j --){ for(int k = 1 ; k < j ; k ++){ if(dp[r][j] < dp[r][j - k] + dp[u][k]){ dp[r][j] = dp[r][j - k] + dp[u][k] ; } } } } } int main(){ // freopen("data.in" ,"r" , stdin) ; // freopen("tmp.txt" ,"w" , stdout) ; while(scanf("%d%d" , &n , &m) , n+m){ init() ; int a ; int b ; m ++ ; for(int i = 1 ; i <= n ; i ++){ scanf("%d%d" , &a , &b) ; G[a].push_back(i); w[i] = b ; } dfs(0) ; printf("%d\n" , dp[0][m]) ; } return 0 ; }