CTSC1997 选课

题目：选课

网址：https://www.luogu.com.cn/problem/P2014

题目描述

学校实行学分制。

每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。

学校开设了 \(N\) 门的选修课程，每个学生可选课程的数量 \(M\) 是给定的。

学生选修了这 \(M\) 门课并考核通过就能获得相应的学分。

在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程的基础上才能选修。

例如《Windows程序设计》必须在选修了《Windows操作基础》之后才能选修。

我们称《Windows操作基础》是《Windows程序设计》的先修课。

每门课的直接先修课最多只有一门。

两门课可能存在相同的先修课。

你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修条件。

假定课程之间不存在时间上的冲突。

输入格式

输入文件的第一行包括两个整数\(N、M\)（中间用一个空格隔开）其中1≤N≤300,1≤M≤N。

接下来N行每行代表一门课，课号依次为1，2，…，\(N\)。

每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。

学分是不超过10的正整数。

输出格式

输出一个整数，表示学分总数。

输入样例：

7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2

输出样例：

13

经典的背包问题。有依赖的背包问题。

大体思路就是：树分治的思想。因为我们仅会两个泛化物品的合并，而对于多个泛化物品，我们则显得尤为吃力。

这道题重点在于多个泛化物品合并操作。也就是树分治的思想。

那么，我们就一一进行合并，将合并成的新的物品在于其他泛化物品操作即可。

代码如下：

#include<iostream>
#include<cstring> 
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int maxn = 300 + 10;
int n, m, k[maxn], s[maxn];
vector <int> son[maxn];
int dp[maxn][maxn];
void dfs(int u)
{
	for(int i = 0; i < son[u].size(); ++ i) dfs(son[u][i]);
	for(int i = 1; i <= m + 1; ++ i) dp[u][i] = s[u];
	
	for(int i = 0; i < son[u].size(); ++ i)
	{
		for(int j = m + 1; j; -- j)
		{
			int &ans = dp[u][j];
			for(int k = 0; k < j; ++ k)
			{
				ans = max(ans, dp[son[u][i]][k] + dp[u][j - k]);
			}
		}
	}
	return;
}
int main()
{
	memset(dp, 0, sizeof(dp));
	for(int i = 0; i <= n; ++ i)
	{
		son[i].clear();
	}
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; ++ i)
	{
		scanf("%d %d", &k[i], &s[i]);
		son[k[i]].push_back(i);
	}
	dfs(0);
	printf("%d\n", dp[0][m + 1]);
	return 0;
}

CTSC1997 选课

原文：https://www.cnblogs.com/zach20040914/p/13215422.html