树形 DP 的一道较为基础的模板题
状态
dp[i][0/1] 为第 i 个员工是否来参加的最大值
转移
先找到根节点
先遍历完它的儿子, 再来更新答案
- dp[i][0]+=max(dp[j][0],dp[j][1]);//j 为 i 的儿子, i 不来, 那 j 可来可不来
- dp[i][1]+=dp[j][0];//j 为 i 的儿子, i 来, 那只能不来
初始
- dp[i][0]=0;// 不来的初始值为 0
- dp[i][1]=r[i];// 来的初始值就是此人的快乐指数
答案
很明显就是大 BOSS 来不来的问题了
max(dp[root][0],dp[root][1]);
完整代码:
- #include<bits/stdc++.h>
- using namespace std;
- const int N=6000+10;
- int n,m;
- int r[N];
- bool v[N];
- vector<int>son[N];
- int dp[N][2];
- inline int read()
- {
- int tot=0,f=1;
- char c=getchar();
- while(c<'0'||c>'9')
- {
- if(c=='-')f=-1;
- c=getchar();
- }
- while(c>='0'&&c<='9')
- {
- tot=tot*10+c-'0';
- c=getchar();
- }
- return tot*f;
- }
- inline void f(int now)
- {
- dp[now][0]=0;
- dp[now][1]=r[now];
- for(int i=0;i<son[now].size();i++)
- {
- int x=son[now][i];
- f(x);
- dp[now][0]+=max(dp[x][0],dp[x][1]);
- dp[now][1]+=dp[x][0];
- }
- }
- int main()
- {
- n=read();
- for(int i=1;i<=n;i++)r[i]=read();
- int x,y;
- for(int i=1;i<n;i++)
- {
- x=read();y=read();
- son[y].push_back(x);
- v[x]=1;
- }
- int root;
- for(int i=1;i<=n;i++)
- if(!v[i])
- {
- root=i;
- break;
- }
- f(root);
- int ans=max(dp[root][1],dp[root][0]);
- cout<<ans<<endl;
- return 0;
- }
来源: https://www.cnblogs.com/hulean/p/10828385.html