[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]=max(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]没有被更新过，所以倒序。

#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]);
}

最后

以上就是知性冰淇淋为你收集整理的[luogu] P2014 [CTSC1997]选课的全部内容，希望文章能够帮你解决[luogu] P2014 [CTSC1997]选课所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。