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;}新闻热点
疑难解答
