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

题目地址:http://poj.org/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 
#include 
using namespace std;const int MAXN = 3005;
const int INF = 0x3f3f3f3f;struct node
{int end,val;
};
vector 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::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");}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！