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;}新聞熱點
疑難解答
