PRoblem: 有很多的士兵需要出征，如果士兵出征那他的上級也必須出征，如果一個士兵的上級是自己，那么說明自己就是老大，最多不超過500個老大，每個士兵有兩個屬性，需要花費的錢和能貢獻的價值，給定允許消費的最大的錢，問最多的貢獻是多少？ Solution: 很明顯可以看到題目的數據結構是一個森林，但是我們可以通過設置一個0節點當做所有老大的父節點，這樣就轉化為了一棵樹，這個問題很像一個背包問題，但有點區別，當一個士兵是葉子時，想一個物品一樣直接更新即可，但是如果它不是一個葉子，那么他還有很多的子節點，這時在進行其它兄弟節點dp時，一開始的初始化已知最優解就很關鍵了，也就是說每一個兄弟節點在動規時都使用的是當前子樹的最優值，這就可以保證這棵子樹動歸完成后是最優解?？梢岳斫鉃檎麄€個動態規劃就是利用每一棵子樹不斷的更新可以購買這棵子樹的解。
#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;}新聞熱點
疑難解答
