本文出自 http://blog.csdn.net/shuangde800
題目連結：hdu-4044
題意
這是一個塔防遊戲，地圖是一個n個編号為1～n的節點的樹， 節點1是敵人的基地，其他葉子節點都是你的基地。
敵人的基地會源源不斷地出來怪獸，為了防止敵人攻進你的基地，你可以選擇造塔。
每個節點最多隻能造一個塔，且節點i可以有ki種塔供你選擇，價錢和攻擊力分别為price_i, power_i
攻擊力power_i，效果是讓敵人經過這個節點時讓敵人的血減少power_i點。
那麼從敵人的基地到你的任意一個基地的路徑，這條路徑上的所有塔的攻擊力之和，就是這個基地的抵抗力。
敵人的攻擊路徑是不确定的，為了保護你的所有基地，你要确定所有基地中抵抗力最低的一個。
你隻有數量為m的錢，問最佳方案，可以抵擋敵人的最大血量是多少？也就是，讓所有基地中抵抗力最低的一個的值盡量大，
最大是多少？
思路：
方法一： 多叉轉二叉
把多叉樹先轉化成“左兒子，右兄弟”的表示方法。會發現形成這樣一種結構圖：
多叉樹：
轉化成“左兒子，右兄弟”的二叉樹：
用二叉樹來思考這道題，會更自然，也更好想
用f[i][j]表示：子樹i, 用j的花費，能防守的最大HP
那麼, 先計算出i和它兒子一起用j的花費能防守的最大HP,
f[i][j] = max{ f[i][j-k] + f[son][k] | 0<=k<=j}
然後和它的兄弟進行狀态轉移：
f[i][j] = max{ min(f[i][j-k], f[brother][k]) | 0<=k<=j}
最終f[1][m]就是答案了.
方法二：
f[u][j]：子樹u, 花j的錢的消滅的最大HP
對于子樹i, 可以選擇配置設定k(0<=k<=j)的花費給它的所有兒子，留j-k給i點花
對于所有的兒子要合理的配置設定使用這k的花費，才可以消滅的最大HP，
用maxSon[u][k]表示所有u的所有兒子使用k的花費，可以消滅的最大HP
我們要先求出maxSon數組, 求這個數組就和分組背包一樣，因為對于每個兒子，
可以選擇配置設定1...k的花費給它，是以不難得到狀态轉移：
maxSon[u][j] = max{ min(maxSon[j-k], f[v][k]) | 0<=k<=j & v是u的兒子}
求出這個數組後，就可以跟新節點u的值了
f[u][j] = max{ f[u][j-k] + maxSon[k] | 0<=k<=j }
小結：
上面兩種方法，因為之前沒做過多叉轉二叉，是以一開始我想到的是方法二的，和@ZeroClock學長想的一樣。而多叉轉二叉是@nothi大神的提醒下知道的，然後我發現轉化成二叉樹來想這題更加自然，也更不容易出錯。
方法一代碼：
/**=====================================================
* This is a solution for ACM/ICPC problem
*
* @source : hdu-4044 GeoDefense
* @description : 樹形dp, 多叉轉二叉
* @author : shuangde
* @blog : blog.csdn.net/shuangde800
* @email : [email protected]
* Copyright (C) 2013/08/27 13:03 All rights reserved.
*======================================================*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MP make_pair using namespace std; typedef pair
PII; typedef long long int64; const double PI = acos(-1.0); const int INF = 0x3f3f3f3f; const int MAXN = 1010; vector
adj[MAXN]; int n, m; int opt[MAXN]; int price[MAXN][52], power[MAXN][52]; bool vis[MAXN]; int f[MAXN][MAXN]; // 左兒子，右兄弟 struct Node{ int left, right; }E[MAXN*2]; inline void initNode(int e) { E[e].left = E[e].right = -1; } // 多叉轉二叉 void buildBinTree(int u, int fa) { initNode(u); int e, last; for (e = 0; e < adj[u].size(); ++e) { int v = adj[u][e]; if (v == fa) continue; initNode(v); last = E[u].left = v; buildBinTree(v, u); ++e; break; } for ( ; e < adj[u].size(); ++e) { int v = adj[u][e]; if (v == fa) continue; initNode(v); E[last].right = v; last = v; buildBinTree(v, u); } } void dfs(int u) { for (int v = m; v >= 0; --v) { for (int j = 0; j < opt[u]; ++j) { if (price[u][j] <= v) f[u][v] = max(f[u][v], power[u][j]); } } // 和兒子的配置設定 if (E[u].left != -1) { int son = E[u].left; dfs(son); for (int i = m; i >= 0; --i) { for (int j = 0; j <= i; ++j) f[u][i] = max(f[u][i], f[u][i-j] + f[son][j]); } } if (E[u].right != -1) { int brother = E[u].right; dfs(brother); for (int i = m; i >= 0; --i) { int tmp = 0; for (int j = 0; j <= i; ++j) tmp = max(tmp, min(f[u][i-j] , f[brother][j])); f[u][i] = tmp; } } } int main(){ int nCase; scanf("%d", &nCase); while (nCase--) { scanf("%d", &n); for (int i = 0; i <= n; ++i) adj[i].clear(); for (int i = 0; i < n - 1; ++i) { int u, v; scanf("%d %d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } scanf("%d", &m); for (int i = 1; i <= n; ++i) { scanf("%d", &opt[i]); for (int j = 0; j < opt[i]; ++j) scanf("%d%d", &price[i][j], &power[i][j]); } // 多叉轉二叉 buildBinTree(1, -1); memset(f, 0, sizeof(f)); dfs(1); printf("%d\n", f[1][m]); } return 0; }
方法二代碼：
/**=====================================================
* This is a solution for ACM/ICPC problem
*
* @source : hdu-4044 GeoDefense
* @description : 樹形dp
* @author : shuangde
* @blog : blog.csdn.net/shuangde800
* @email : [email protected]
* Copyright (C) 2013/08/27 13:03 All rights reserved.
*======================================================*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MP make_pair using namespace std; typedef pair
PII; typedef long long int64; const double PI = acos(-1.0); const int INF = 0x3f3f3f3f; const int MAXN = 1010; vector
adj[MAXN]; int n, m; int opt[MAXN]; int price[MAXN][52], power[MAXN][52]; int f[MAXN][MAXN]; // tree dp void dfs(int u, int fa) { // init for (int v = 0; v <= m; ++v) { for (int j = 0; j < opt[u]; ++j) if (price[u][j] <= v) f[u][v] = max(f[u][v], power[u][j]); } // 如果葉子節點, 退出 if (adj[u].size()==1 && u!=1) { return; } // maxSon[i]: 表示所有兒子花費i時，可以消滅的最大HP int maxSon[210]; memset(maxSon, INF, sizeof(maxSon)); for (int e = 0; e < adj[u].size(); ++e) { int v = adj[u][e]; if (v==fa) continue; dfs(v, u); for (int i = m; i >= 0; --i) { int maxx = 0; for (int j = 0; j <= i; ++j) { maxx = max(maxx, min(maxSon[i-j], f[v][j])); } maxSon[i] = maxx; } } for (int i = m; i >= 0; --i) { for (int k = 0; k <=i; ++k) { f[u][i] = max(f[u][i], f[u][i-k] + maxSon[k]); } } } int main(){ int nCase; scanf("%d", &nCase); while (nCase--) { scanf("%d", &n); for (int i = 0; i <= n; ++i) adj[i].clear(); for (int i = 0; i < n - 1; ++i) { int u, v; scanf("%d %d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } scanf("%d", &m); for (int i = 1; i <= n; ++i) { scanf("%d", &opt[i]); for (int j = 0; j < opt[i]; ++j) scanf("%d%d", &price[i][j], &power[i][j]); } memset(f, 0, sizeof(f)); dfs(1, -1); printf("%d\n", f[1][m]); } return 0; }