题目描述
Ural大学有N名职员,编号为1~N。
他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。
每个职员有一个快乐指数,用整数 Hi 给出,其中 1≤i≤N。
现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。
在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。
输入格式
第一行一个整数N。
接下来N行,第 i 行表示 i 号职员的快乐指数Hi。
接下来N-1行,每行输入一对整数L, K,表示K是L的直接上司。
最后一行输入0,0。
输出格式
输出最大的快乐指数。
数据范围
1≤N≤6000,
−128≤Hi≤127
样例
输入样例:
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
算法1
(树形dp加记忆化减低复杂度)
如果是线型的一串一维数组的话 不能选择相邻的数字 要让选择的数的和最大
那么就有递推方程dp[i] = max(dp[i-1],dp[i-2] + a[i])
max里面前一个式子代表我不选a[i] 那么就能从dp[i-1] 转移过来
后面一个代表我选了这个 那么就是从dp[i-2] + a[i] 转移过来
两者取最大值就是我们需要的答案 那么这题的话就可以用这个思想
如果我们选择了这个节点的值的话 我们就只能从这个节点出发的下下一层转移了 下一层不能选了
如果我们不选这个节点 我们直接从下一层节点转移就好了 两者取最大值
具体看代码
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 6010;
int val[maxn] , in[maxn];
int dp[maxn] = {0};// 记忆化优化 相当于剪枝了
vector<int> g[maxn]; // 记录树
int dfs(int root)
{
int tans = dp[root]; // 如果前面搜索到了就直接输出就好了
if(tans!=0) return tans;
if(g[root].size() == 0) return val[root]; // 递归到叶子节点直接返回
int ans = val[root] , ans1 = 0 ;// ans 代表我选择了这个节点 ans1 代表我不选择这个节点
for(int i = 0 ; i < g[root].size(); i++) // 第一层
{
for(int j = 0 ; j < g[g[root][i]].size(); j++)
{
ans += dfs(g[g[root][i]][j]);// 那么按照刚才的思路 ans就是从下下一层转移
}
ans1 += dfs(g[root][i]);// 我不选这个就可以直接从这一层转移
tans = max(ans1,ans); // 两者取一下最大值
}
return dp[root] = tans; // 记忆化 避免很多的多余运算
}
int main()
{
int n;
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>val[i];
}
int u,v;
while(cin>>u>>v&&u!=0)
{
g[v].push_back(u);
in[u]++;
}
int root , ans = 0;
for(int i = 1; i <= n; i++)
{
if(in[i]==0) root = i; // 找到根节点开始dfs
}
ans = dfs(root);
cout<<ans<<endl;
}
想问一下这里不就只需要遍历一遍树吗,记忆化避免了哪里的重复计算呢🙄🙄🙄
hack
7
-1 -1 -1 -1 -1 -1 3
1 3
2 3
6 4
7 4
4 5
3 5
大佬,我也这样写的,发现很少题解是这样的。