题目描述：
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？
输入格式
第一行有两个整数 $N$ , $M$ 用空格隔开。( $1 \leq N \leq 300$ , $1 \leq M \leq 300$ )
接下来的 $N$ 行,第 $I+1$ 行包含两个整数 $k_i $ 和 $s_i$ , $k_i$ 表示第I门课的直接先修课， $s_i$ 表示第I门课的学分。若 $k_i=0$ 表示没有直接先修课（ $1 \leq {k_i} \leq N$ , $1 \leq {s_i} \leq 20$ ）。
输出格式
只有一行，选 $M$ 门课程的最大得分。
数据范围：
$1\le N \le 300,1\le M\le 300, 1\le s_i \le 20$
题解：
依赖背包，用
代码：
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
44
45
46
47
48
49
50
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 3e2 + 10;
const int maxm = 3e2 + 10;
int t, n, m, k;
vector<int> g[maxn];
int dp[maxn][maxm];
int a[maxn];
void dfs(int u)
{
for (int j = 1; j <= m; ++j)
dp[u][j] += a[u];
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
dfs(v);
for (int j = m; j >= 1; --j)
{
for (int k = 0; k <= j - 1; ++k)
{
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
}
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
read(n, m);
m++;
for (int i = 1, p; i <= n; ++i)
{
read(p, a[i]);
g[p].emplace_back(i);
}
dfs(0);
cout << dp[0][m] << endl;
return 0;
}
|