题目链接:点击打开链接
题意:
给定n个点,
每个点的豆子数量
下面是一棵树
再给出起点
每走到一个点,就会把那个点的豆子吃掉一颗。
问:回到起点最多能吃掉多少颗豆子
思路:树形dp
对于当前节点u,先把子节点v都走一次。
然后再往返于(u,v) 之间,直到u点没有豆子或者v点没有豆子。
dp[u] 表示u点的最大值。a[u] 是u点剩下的豆子数。
#include <cstdio> #include <vector> #include <algorithm> #include <iostream> using namespace std; #define N 100002 #define ll long long int n, root; vector<int>G[N]; bool cmp(int a, int b){return a>b;} int a[N]; ll dp[N];//dp[i] 表示 回到i点的最大值 void dfs(int u, int fa){ dp[u] = 1; vector<ll>s; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(v == fa || a[v] == 0)continue; a[v]--; dfs(v, u); if(dp[v]) s.push_back(dp[v]); } sort(s.begin(), s.end(),cmp); for(int i = 0; a[u] && i < s.size(); i++) a[u]--, dp[u] += s[i] +1; for(int i = 0; a[u] && i < G[u].size(); i++) { int v = G[u][i]; if(v == fa || a[v] == 0)continue; dp[u] += 2LL * min(a[u], a[v]); a[u] -= min(a[u], a[v]); } } int main() { int i, u, v; while(~scanf("%d", &n)) { for(i = 1; i <= n; i++) scanf("%d",&a[i]), G[i].clear(); for(i = 1; i < n; i++) { scanf("%d %d",&u,&v); G[u].push_back(v); G[v].push_back(u); } scanf("%d",&root); dfs(root, root); cout<<dp[root]-1<<endl; } return 0; }
Codeforces 77C 树形dp + 贪心,布布扣,bubuko.com
原文:http://blog.csdn.net/qq574857122/article/details/38587415