树形dp(2) P1352 没有上司的舞会

胡乱分析

这个题目就是相对简单了,我基本想到了8成的转移方程,但是还是无奈dfs功底有点差写不出来…..
转移方程就是当前选这个父亲节点或者不选这个父亲节点的问题,如果选这个父亲节点的话那么加上子节点不选的,不选那么加上子节点不选和选的最大值
也就是说
dp[p][0]+=max(dp[s][0],dp[s][1])
dp[p][1]+=dp[s][0]
其中p是父亲节点s是子节点0代表不选1代表选那么dfs即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
int num[6666],dp[6666][6],bk[6666];
vector<int> G[6666];
void dfs(int p)
{
dp[p][0]=0;
dp[p][1]=num[p];
for(int i=0;i<G[p].size();i++)
{
dfs(G[p][i]);
dp[p][0]+=max(dp[G[p][i]][0],dp[G[p][i]][1]);
dp[p][1]+=dp[G[p][i]][0];
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,rt;
cin>>n;
for(int i=1;i<=n;i++)
cin>>num[i];
for(int i=1;i<=n-1;i++)
{
int st,ed;
cin>>ed>>st;
bk[ed]++;
G[st].push_back(ed);
}
for(int i=1;i<=n;i++)
if(!bk[i])
{
rt=i;
break;
}
dfs(rt);
cout<<max(dp[rt][0],dp[rt][1]);
}
就算是一分钱,也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
本文首发于baccano 博客( http://baccano.fun ),版权所有,侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆?---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%