<— 麻烦点亮一下旁边这个好看的向上的三角形
推荐一下$\color{#FF00FF}{算法基础课 第五章 动态规划全题解(正在完善)}$
题目描述
$Ural$ 大学有 $N$ 名职员,编号为 $1∼N$。
他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。
每个职员有一个快乐指数,用整数 $H_i$ 给出,其中 $1≤i≤N$。
现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。
在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。
输入格式
第一行一个整数 $N$。
接下来 $N$ 行,第 $i$ 行表示 $i$ 号职员的快乐指数 $H_i$。
接下来 $N−1$ 行,每行输入一对整数 $L,K$,表示 $K$ 是 $L$ 的直接上司。
输出格式
输出最大的快乐指数。
数据范围
$1≤N≤6000$,
$−128≤H_i≤127$
输入样例:
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
输出样例:
5
题意简化
这道题题目看上去花里胡哨的,但其实挺好理解的
前$N$行表示第$i$号职工的快乐指数
后面的$N - 1$行输入两个整数$L,K$,表示 $K$ 是 $L$ 的直接上司,如图。
要求使得所有参会职员的快乐指数总和最大。
在这儿讲解一下样例
根据这个样例,我们可以画出一张图(如果还不知道样例是什么意思的看上面),如下:
那输出样例的 $5$ 是怎么来的呢?
请看:
根据画图得出,$⑤$ 是根节点(校长)。
我们知道样例中每个节点的快乐值都为 $1$,所以决定最大快乐值的是节点的数量在这个样例里,我们必须选校长,为什么呢?
比如我们选了 $③$,那他的下属全部$KO$,或者选了 $④$,也是一样
那我们的最大快乐值就变成了 $3$,错误
只有我们选了 $⑤$,那剩下的 $①$、 $②$、 $⑥$、 $⑦$才能苟活被选中我们现在选了 $⑤$,那我们就可以有五个人参加,且快乐值是最大的,为 $5$,选中的清晰,如图:
发现什么了吗?
- 当不选 $i$ 节点时,影响最大高兴值的节点为$i$的子节点或其他节点
- 当选 $i$ 节点时,影响最大高兴值的节点只为$i$的子节点
由此我们可以得出状态转移方程:
- 当 $f[i][1]$ 时表示选 $i$ 号节点。
那么很明显 $i$ 号节点的快乐值需要算上
然后我们知道,如果选了这个点,它的所有字节点都是不能选的,所以我们应该给它加上 $f[j][0]$ - 当 $f[i][0]$ 时表示不选 $i$ 号节点。
这时我们不需要加上 $i$ 号点的快乐值
如果不选这个点,它的子节点可以选也可以不选,所以我们应该给它加上 $max{f[j][0],f[j][1]}$
弱弱地问一句,题目看懂并理解了吧…
算法1
(树形DP) $O(n)$
看图:
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 6010;
int n;
int happy[N]; //每个职工的高兴度
int f[N][2]; //上面有解释哦~
int e[N],ne[N],h[N],idx; //链表,用来模拟建一个树
bool has_father[N]; //判断当前节点是否有父节点
void add(int a,int b){ //把a插入树中
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
void dfs(int u){ //开始求解题目
f[u][1] = happy[u]; //如果选当前节点u,就可以把f[u,1]先怼上他的高兴度
for(int i = h[u];~i;i = ne[i]){ //遍历树
int j = e[i];
dfs(j); //回溯
//状态转移部分,上面有详细讲解~
f[u][0] += max(f[j][1],f[j][0]);
f[u][1] += f[j][0];
}
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&happy[i]); //输入每个人的高兴度
memset(h,-1,sizeof h); //把h都赋值为-1
for(int i = 1;i < n;i ++){
int a,b; //对应题目中的L,K,表示b是a的上司
scanf("%d%d",&a,&b); //输入~
has_father[a] = true; //说明a他有上司
add(b,a); //把a加入到b的后面
}
int root = 1; //用来找根节点
while(has_father[root]) root ++; //找根节点
dfs(root); //从根节点开始搜索
printf("%d\n",max(f[root][0],f[root][1])); //输出不选根节点与选根节点的最大值
return 0;
}
$$共190行$$
一位蒟蒻AC之后兴高采烈地准备发题解并写好了注释然后看见大佬的题解就%%%%%%并弱弱地附上非官方代码注释补全
%%%
邻接表没看懂呜呜可否画下图
邻接表不属于树形dp内容跟,可以去图论那一章
他真的,我哭死
最后main函数里为什么是for(int i=n+1;i<2*n;i++)
while (has_fa[root])root++; 为什么要排除根节点呢,跟节点可以选可以不选啊
?这不是在找根节点编号吗,为什么排除根节点了
用 $1$ 到 $n - 1$ 就行的,应该是等价的
orz
QwQ
比如我们选了③,那他的下属全部KO,或者选了④,也是一样
那我们的最大快乐值就变成了2,错误
这里最大快乐因该是变成三吧, 3, 6, 7,并不是直接关系
哦逝的
已改正
后面我有时间改个图吧,好丑…
图改好了
while(has_father[root]) root ++;
%%%
emmm…
发现有些地方写得不是很清楚或者逝废话
更改了一些地方,应该会更容易理解
动态归化(
不要再讽刺我的语文水平了大佬图里的动态规划写成规化了hh
古咕顾!
啊?
图现在改好了QwQ
orz
QwQ
为什么f【6010】【1】就会出问题
越界了,$n$ 只到 $6000$ 啊。
感谢佬
QwQ
大佬有练过字吗?字好好看
二年级的时候练过(
字好好看
QwQ
太简单了呀
是不是因为是有向图且没有环因此不用加st[]数组来判断某个节点是否已经遍历过了?
是的,类似记忆化搜索
大佬6滴
QwQ
女少口啊
这个代码现在好像过不了了
过的了,你自己可能写错了
刚刚测的
奇怪了,突然发现是其中一个样例测的时候没过,Segmentation Fault了,交的话能AC的
字挺好看
牛逼
为什么建树要用邻接表?(蒟蒻疑惑
不一定要用邻接表啊
哦