PRoblem: 有很多的士兵需要出征，如果士兵出征那他的上級(jí)也必須出征，如果一個(gè)士兵的上級(jí)是自己，那么說(shuō)明自己就是老大，最多不超過(guò)500個(gè)老大，每個(gè)士兵有兩個(gè)屬性，需要花費(fèi)的錢(qián)和能貢獻(xiàn)的價(jià)值，給定允許消費(fèi)的最大的錢(qián)，問(wèn)最多的貢獻(xiàn)是多少？ Solution: 很明顯可以看到題目的數(shù)據(jù)結(jié)構(gòu)是一個(gè)森林，但是我們可以通過(guò)設(shè)置一個(gè)0節(jié)點(diǎn)當(dāng)做所有老大的父節(jié)點(diǎn)，這樣就轉(zhuǎn)化為了一棵樹(shù)，這個(gè)問(wèn)題很像一個(gè)背包問(wèn)題，但有點(diǎn)區(qū)別，當(dāng)一個(gè)士兵是葉子時(shí)，想一個(gè)物品一樣直接更新即可，但是如果它不是一個(gè)葉子，那么他還有很多的子節(jié)點(diǎn)，這時(shí)在進(jìn)行其它兄弟節(jié)點(diǎn)dp時(shí)，一開(kāi)始的初始化已知最優(yōu)解就很關(guān)鍵了，也就是說(shuō)每一個(gè)兄弟節(jié)點(diǎn)在動(dòng)規(guī)時(shí)都使用的是當(dāng)前子樹(shù)的最優(yōu)值，這就可以保證這棵子樹(shù)動(dòng)歸完成后是最優(yōu)解?？梢岳斫鉃檎麄€(gè)個(gè)動(dòng)態(tài)規(guī)劃就是利用每一棵子樹(shù)不斷的更新可以購(gòu)買(mǎi)這棵子樹(shù)的解。
#include<cstdio>#include<iostream>#include<sstream>#include<cstdlib>#include<cmath>#include<cctype>#include<string>#include<cstring>#include<algorithm>#include<stack>#include<queue>#include<set>#include<unordered_set>#include<map>#include<unordered_map>#include<ctime>#include<vector>#include<fstream>#include<list>#include<numeric>#include<functional>using namespace std;typedef long long ll;typedef unsigned long long ull;#define ms(s) memset(s,0,sizeof(s))const double PI = 3.141592653589;const int INF = 0x3fffffff;int c[100010], v[100010];vector<int> Tree[100010];int dp[505][10010];int n, maxg;void solve(int root, int g) { for(int i = 0; i < Tree[root].size(); i++) { int child = Tree[root][i]; if(Tree[child].empty()) { for(int j = g; j >= c[child]; j--) { dp[root][j] = max(dp[root][j], dp[root][j-c[child]]+v[child]); } } else { for(int j = 0; j <= g-c[child]; j++) { dp[child][j] = dp[root][j]; } solve(child, g-c[child]); for(int j = g; j >= c[child]; j--) { dp[root][j] = max(dp[root][j], dp[child][j-c[child]]+v[child]); } } }}int main() {// freopen("/Users/really/Documents/code/input","r",stdin); // freopen("/Users/really/Documents/code/output","w",stdout); ios::sync_with_stdio(false); int fa; while(cin >> n >> maxg) { //init for(int i = 0; i <= 500; i++) Tree[i].clear(); ms(dp); for(int i = 1; i <= n; i++) { cin >> c[i] >> v[i] >> fa; if(fa == i) Tree[0].push_back(i); else Tree[fa].push_back(i); } solve(0, maxg); cout << dp[0][maxg] << endl; } return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
