[luogu] P2014 [CTSC1997]选课

153 阅读 0 评论 101 点赞

我是靠谱客的博主知性冰淇淋，这篇文章主要介绍[luogu] P2014 [CTSC1997]选课，现在分享给大家，希望可以做个参考。

题目详情
题目分析：

f[i][j]表示以i为根节点，选j个节点，获得的最大分数
dfs(u)的作用就是算出以u为节点时，分别选0~m个节点各自的最大值
解释为什么k从j - 1开始，u是v的父节点，选v必须先选u这节先修课。假设如果k能取到j，有
$f [u] [j] = m a x (f [u] [j], f [u] [0] + f [v] [j]);$
由上式我们知道不可能以v为节点选了j个，而它的父节点只选了零个，这是不可能的。所以k < j.
解释
$f [u] [j - k] + f [v] [k]$
u有很多子节点，v只是其中一个，当以v为根节点时选k节课时，剩下的同父子节点只能选j - k个。
解释m要倒序遍历，因为f[u][j - k]转移到f[u][j]，更新f[u][j]时，保证f[u][j - k]没有被更新过，所以倒序。

复制代码

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
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, score[333], a, f[333][333], head[333], cnt;
struct edge{
int to, next;
} e[333];
void add(int u, int v){
e[++cnt] = edge{v, head[u]};//c++11标准的写法
head[u] = cnt;
}
void dfs(int u){
f[u][1] = score[u];
for (int i = head[u]; i; i = e[i].next){
int v = e[i].to;
dfs(v);
for (int j = m; j > 0; j--)
for (int k = j - 1; k > 0; k--)
f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++){
scanf("%d%d", &a, score + i);
add(a, i);
}
m++;//0节点也选了，一共m + 1 个节点，所以m++;
dfs(0);//从零节点开始搜索。
printf("%dn", f[0][m]);
}