http://acm.hdu.edu.cn/showproblem.php?pid=1561

做樹(shù)形dp比較小。

先上網(wǎng)學(xué)習(xí)下，總結(jié)下套路。

dp[i][j]表示在第i個(gè)節(jié)點(diǎn)，有j個(gè)名額選的時(shí)候的最大ans，

初始值dp[i][1---tot] = val[i]，也就是每一個(gè)節(jié)點(diǎn)，有1、2、3、。。tot個(gè)選擇的時(shí)候，最大值是自己

然后dfs，回溯的時(shí)候，對(duì)于每一個(gè)兒子，都可以用來(lái)更新爸爸，枚舉爸爸選了j個(gè)，j >= 1因?yàn)橹挥邪职诌x了，兒子才能選。

分配給當(dāng)前回溯的兒子v選了j - k個(gè)，其中 ? 1 <= k <= j，還有一部分是k，是爸爸保留的名額。

dp[cur][j] = max(dp[cur][j], ? dp[cur][k] + dp[v][j - k]); // j - k可能等于0，也就是不選兒子。

#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL;const int maxn = 200 + 20; struct Edge {int u, v, tonext; }e[maxn * 2]; int num, first[maxn]; void addEdge(int u, int v) {e[num].u = u, e[num].v = v, e[num].tonext = first[u];first[u] = num++; } struct Node {int cost, val; }a[maxn]; int tot, n; int dp[maxn][maxn]; void dfs(int cur) {for (int i = first[cur]; ~i; i = e[i].tonext) {int v = e[i].v;dfs(v);for (int j = tot; j >= 1; --j) { // 當(dāng)前這個(gè)爸爸最多有j個(gè)選for (int k = 1; k <= j; ++k) { //更新?tīng)顟B(tài)，j - k表示留j - k個(gè)名額給兒子v選dp[cur][j] = max(dp[cur][j], dp[cur][k] + dp[v][j - k]);} //其中j不能等于0， 因?yàn)榘职种辽僖x1個(gè)才能選兒子 }} } void work() {memset(dp, 0, sizeof dp);num = 0;memset(first, -1, sizeof first);tot++;for (int i = 1; i <= n; ++i) {int per, val;cin >> per >> val;a[i].val = val;addEdge(per, i);for (int j = 1; j <= tot; ++j) {dp[i][j] = val;}}dfs(0);printf("%d\n", dp[0][tot]); }int main() { #ifdef localfreopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endifwhile (cin >> n >> tot && (tot + n)) work();return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/liuweimingcprogram/p/7224043.html

總結(jié)

以上是生活随笔為你收集整理的hdu 1561 The more, The Better 树形dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。