POJ-1155 TELE（树形dp+背包）

题目地址:/problem?id=1155

基础的树形dp，在以i为根结点的子树上选择儿子的过程就是做一次0-1背包，背包体积变化，物品体积变化。

dp[i][j]表示以i为根结点的子树选择j个用户的最大代价，转移方程为dp[i][j] = max(dp[i][j],dp[i][j-k]+dp[son[i]][k]);

#include <stdio.h>#include <vector>using namespace std;const int MAXN = 3005;const int INF = 0x3f3f3f3f;struct node{int end,val;};vector<node> v[MAXN];int cost[MAXN],dp[MAXN][MAXN];int n,m;inline node make_node(int end,int val){node a;a.end = end;a.val = val;return a;}inline int max(int a,int b){ return a < b ? b : a; }int dfs(int root){int sum = 1;vector<node>::iterator it;for(it=v[root].begin();it!=v[root].end();it++){sum += dfs((*it).end);}for(it=v[root].begin();it!=v[root].end();it++)for(int j = sum;j >= 0;j--)for(int k = 0;k <= j;k++)dp[root][j] = max(dp[root][j],dp[(*it).end][k]+dp[root][j-k]-(*it).val);//printf("root = %d sum = %d\n",root,sum);return sum;}int main(){int num,a,b;while(scanf("%d%d",&n,&m) == 2){for(int i = 1;i <= n;i++) v[i].clear();for(int i = 1;i <= n-m;i++){scanf("%d",&num);for(int j = 1;j <= num;j++){scanf("%d%d",&a,&b);v[i].push_back(make_node(a,b));}}for(int i = n-m+1;i <= n;i++) scanf("%d",&cost[i]);for(int i = 1;i <= n;i++)for(int j = 0;j <= n;j++) dp[i][j] = -INF;for(int i = 1;i <= n;i++) dp[i][0] = 0;for(int i = n-m+1;i <= n;i++) dp[i][1] = cost[i];dfs(1);bool find = 0;for(int i = n;i >= 1;i--){if(dp[1][i] >= 0){find = 1;printf("%d\n",i);break;}}if(!find) printf("0\n");}}