題意是說(shuō)在一個(gè)洞穴中有許多房間，每個(gè)房間中有一些蟲(chóng)子和大腦，這些房間之間用隧道相連形成一棵樹(shù)，士兵們殺蟲(chóng)子的能力有限，也可以直接殺死蟲(chóng)子而不消耗士兵戰(zhàn)斗力，但這樣就無(wú)法得到房間中的大腦，士兵們不能走回頭路，問(wèn)給定士兵數(shù)量時(shí)能得到的大腦最大值。

在樹(shù)上進(jìn)行動(dòng)態(tài)規(guī)劃，對(duì)于每個(gè)節(jié)點(diǎn)來(lái)說(shuō)，選擇了它，就要損失士兵戰(zhàn)斗力，不選擇它，就可以將這些省下來(lái)的士兵戰(zhàn)斗力用在后面的房間中，后面的房間將最優(yōu)選擇傳遞到當(dāng)前位置，以此來(lái)判斷從而得到最優(yōu)解。
轉(zhuǎn)移方程：dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i ][ j-k ]+dp[ son(i) ][ k ])

dp[ i ][ j ] 表示以節(jié)點(diǎn) i 為根節(jié)點(diǎn)時(shí)消耗 j 個(gè)士兵所能得到的最大大腦數(shù)。

開(kāi)始的時(shí)候直接將每個(gè)士兵按戰(zhàn)斗力分成每個(gè)戰(zhàn)斗力為 1 的士兵，也就是說(shuō)將士兵數(shù)量乘以 20 ，企圖直接可以用士兵數(shù)和蟲(chóng)子數(shù)進(jìn)行加減運(yùn)算，但是這樣很明顯是錯(cuò)誤的，因?yàn)槿绻粋€(gè)房間中的蟲(chóng)子數(shù)模 20 不為零，也就是說(shuō)并不能完全發(fā)揮一個(gè)士兵的戰(zhàn)斗力時(shí)，要取到這個(gè)房間的大腦，就需要再消耗一個(gè)士兵，即士兵戰(zhàn)斗力并不等于士兵手中的子彈數(shù)（這樣說(shuō)好像更復(fù)雜了，意思就是每個(gè)士兵不一定會(huì)殺滿 20 只蟲(chóng)子）。

還有一點(diǎn)就是士兵數(shù)是可以為零的，但是必須要有人進(jìn)去才能得到大腦，無(wú)論里面是否有蟲(chóng)子。

代碼如下：

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXN = 110; 4 int N,M; 5 struct Node 6 { 7 int enemy,aim; 8 }node[MAXN];//存儲(chǔ)所有節(jié)點(diǎn)上的信息 9 int dp[MAXN][MAXN];//dp[i][j]表示根節(jié)點(diǎn)為 i 時(shí)，用掉 j 個(gè)士兵獲得的最大值 10 int mp[MAXN][MAXN];//存圖，mp[i][0]表示與節(jié)點(diǎn) i 相連的邊的數(shù)目 11 bool vis[MAXN];//記錄節(jié)點(diǎn)的訪問(wèn)情況 12 void dfs(int root) 13 { 14 vis[root] = true; 15 int num = (node[root].enemy+19)/20;//獲得當(dāng)前節(jié)點(diǎn)需要的士兵數(shù)目 16 for(int i = num; i <= M; i++) dp[root][i] = node[root].aim; 17 for(int i = 1; i <= mp[root][0]; i++)//開(kāi)始遍歷與根節(jié)點(diǎn)相連的子節(jié)點(diǎn) 18 { 19 int u = mp[root][i]; 20 if(vis[u]) continue; 21 dfs(u); 22 for(int j = M; j >= num; j--) 23 for(int k = 1; j+k <= M; k++) 24 if(dp[u][k])//判斷是否應(yīng)該取當(dāng)前節(jié)點(diǎn) u 25 dp[root][j+k] = max(dp[root][j+k],dp[root][j]+dp[u][k]); 26 } 27 } 28 int main() 29 { 30 int a,b; 31 while(scanf("%d%d",&N,&M)) 32 { 33 if(N == -1 && M == -1) break; 34 memset(vis,0,sizeof(vis)); 35 memset(dp,0,sizeof(dp)); 36 memset(mp,0,sizeof(mp)); 37 for(int i = 1; i <= N; i++) 38 scanf("%d%d",&node[i].enemy,&node[i].aim); 39 for(int i = 1; i < N; i++) 40 { 41 scanf("%d%d",&a,&b); 42 mp[a][0]++; 43 mp[b][0]++; 44 mp[a][mp[a][0]] = b; 45 mp[b][mp[b][0]] = a; 46 } 47 if(M==0) puts("0");//有可能己方?jīng)]有士兵，但要求至少要有人進(jìn)去 48 else 49 { 50 dfs(1); 51 printf("%d\n",dp[1][M]); 52 } 53 54 } 55 return 0; 56 } View Code

這道題還是借鑒了很多大佬的博客才做出來(lái)的，感謝這些大佬的分享 ^_^

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

總結(jié)

以上是生活随笔為你收集整理的HDU 1011(星河战队 树形DP)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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