本文共 907 字,大约阅读时间需要 3 分钟。
本文出自
题意:
给出一棵树 每个节点有权值 要求父节点和子节点不能同时取 求能够取得的最大值
思路:
树形dp的入门题
f[u][0]表示以u为顶点的子树,不选u点的情况下最大值 f[u][1]表示以u为顶点的子树,选u点的情况下最大值 那么, f[u][0] = sum{ max{f[v][0], f[v][1]}, v是u的儿子节点}; //当不选u点时,它的儿子节点可以不选也可以选 f[u][1] = val[u] + sum{f[v][0], v是u的儿子节点} //当选了u点时,它的儿子节点必须是不能选代码:
/**========================================== * This is a solution for ACM/ICPC problem * * @author: shuangde * @blog: blog.csdn.net/shuangde800 * @email: zengshuangde@gmail.com *===========================================*/#include#include #include #include #include #include #include using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f;const double PI = acos(-1.0);const int MAXN = 6010;vector adj[MAXN];int indeg[MAXN];int val[MAXN];int f[MAXN][2];int vis[MAXN];int n, m;void dfs(int u){ vis[u] = true; f[u][0] = 0; f[u][1] = val[u]; for(int i=0; i