时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 119 总提交人数: 123
题目描述
新年到了, 白兔家族要搞大大的聚会. 但是并不是每只白兔都是同一辈分的, 于是便有一棵以老白兔为根的家族树.
每只白兔都有它们自己唯一的整数编号 (范围在 1 到 N 之间), 并且对应一个参加聚会所得的开心值. 为了使每个参加聚会的白兔都巨开心, 老白兔想让每只白兔和他的上一代白兔不会同时参加聚会.
求参加聚会的白兔获得的最大总开心值.
输入
输入的第一行是一个整数 N,1<= N <= 6000
以下的 N 行是对应的 N 个白兔的开心值 (开心值是一个从 - 128 到 127 之间的整数)
接着是白兔的家族树, 树的每一行格式如下: 每行输入一对整数 L,K. 表示第 K 个白兔是第 L 个白兔的上一代. 输入以 0 0 表示结束
输出
参加聚会的白兔获得的最大总开心值
输入样例
- 7
- 1
- 1
- 1
- 1
- 1
- 1
- 1
- 1 3
- 2 3
- 6 4
- 7 4
- 4 5
- 3 5
- 0 0
输出样例
5
AC 代码
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #define maxn 6007
- using namespace std;
- int n;
- int dp[maxn][2],father[maxn];
- void tree_dp(int node)
- {
- int i;
- for(int i=1;i<=n;i++) // 对树遍历. 树的深度游戏先搜索
- {
- if(father[i]==node)
- {
- tree_dp(i);
- dp[node][1]+=dp[i][0];
- dp[node][0]+=max(dp[i][0],dp[i][1]);
- }
- }
- }
- int main()
- {
- int a,b;
- int root=0;
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&dp[i][1]);
- }
- scanf("%d%d",&a,&b);
- while(!(a==0&&b==0))
- {
- father[a]=b;
- scanf("%d%d",&a,&b);
- }
- root=b;
- // 找到根节点
- while(father[root])
- {
- root=father[root];
- }
- // 从根节点开始 dp
- tree_dp(root);
- printf("%d\n",max(dp[root][0],dp[root][1]));
- }
1. 求相邻节点不同时取的最大节点权值和.
2. 考虑序列中相邻不同取的 dp:f[i][0] 表示前 i 个, i 不取的最优值; f[i][1] 表示前 i 个, i 取的最值;
同理到树形 dp:f[i][0] 表示 i 为根的子树中, i 不取的最优值; f[i][1] 同理.
3. 则在 dfs 过程中, 顺道 dp;
4.f[i][0] = ∑max(f[j][1], f[j][0]),j 为 i 的儿子;
f[i][1] = a[i] + ∑f[j][0],j 为 i 的儿子, a[i] 为 i 自身的价值.
5. 答案为 max(f[root][0], f[root][1])
6. 注: 此题由于树的结构的特殊性, 自顶向下生成时并不会产生子问题的重复计算 (每棵子树只对它的父节点产生贡献, 这棵子树的信息只被用到一次)
来源: http://www.bubuko.com/infodetail-2878796.html