很烦啊,最近复习图论,贼艰难,很多题目基本多多少少都要用树形dp。而我专注于搞图论和数据结构,dp完全就是略知一二,逃避没有用,不会就去学,碰到困难就去面对。

树上dp其实跟普通的dp差不多,甚至会比普通的dp写起来简单,但是前提是要理解。

例题

洛谷P1352这个真的是典中典了,我看几乎所有的技术博客都会拿这个当作树形dp的入门题,那我也不例外。

题目分析

某大学有 $n$ 个职员,编号为 $1\ldots n$。

他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。

现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$,但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。

所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。


其实我觉得这个跟有依赖的背包题有异曲同工之妙,不通的是,他们不是依赖,而是互斥,选了一个人之后则不能选另一个人。而依赖背包则是选了一个则必须选另外一个,当然另外一个没有这个限制,否则两个物品直接合并一个物品啦。

这里很明显就是 $n$ 个人 $n-1$ 对关系,可以算做一棵树,但是这棵树是有向的,最顶级的那个上司就是树根了。这里我们肯定得先建一个有向图来保存这个关系,然后我们需要自底向上分析策略。对于每一个叶子节点,它们没有下级,对他们来说只有参加或者不参加,这里我们设 $dp[i][0]$ 为第 $i$ 个人不来参加的最优解,$dp[i][1]$ 为第 $i$ 个人来参加的最优解,注意这个最优解是对于它以及它的所有子孙节点的最优解。我们假设节点 $i$ 有k个节点分别为 $a_1,a_2\dots a_k$ ,那么可以写出如下状态转移方程。

$dp[i][1] = \sum _{x=1} ^{k} dp[a_x][0]$

$dp[i][0] = \sum _{x=1} ^{k} \max(dp[a_x][0],dp[a_x][1])$

这里很明显,对于本人不参加,那么自己的下属可参加可不参加,但是自己参加了自己的下属一定不能参加,而自己不参加选择下属参加还是不参加也是选取最优结果的,因此能得到上面的状态转移方程。然后就是最基本的树的操作了:建边,找根,dfs,状态转移,最后结果就是 $\max(dp[root][1],dp[root][0])$,所以这道题是真的入门题。

标程

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
41
42
43
#include<bits/stdc++.h>
using namespace std;
#define maxn 6500
struct eee{
int to;
int next;
}edge[maxn];
int root[maxn],degree[maxn],cnt,n,dp[maxn][2];
void add(int x,int y){
degree[y]++;
edge[++cnt].next=root[x];
edge[cnt].to=y;
root[x]=cnt;
return ;
}
void dfs(int x){

for(int i=root[x];i;i=edge[i].next){
int v=edge[i].to;
dfs(v);
dp[x][0]+=max(dp[v][1],dp[v][0]);//状态转移方程
dp[x][1]+=dp[v][0];
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
cin>>dp[i][1];
}
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(y,x);
}
for(int i=1;i<=n;i++){
if(!degree[i]){//找根
dfs(i);
printf("%d\n",max(dp[i][1],dp[i][0]));
}
}
return 0;
}