题目#

[CTSC1997] 选课#

题目描述#

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？

$1 \leq N \leq 300$ , $1 \leq M \leq 300$

题解#

树上dp+背包

设f[u][i][j]表示以u为根的子树中，前i颗u的子树，选j颗的获得的最大学分

然后发现和01背包差不多，只不过需要枚举一下u中的每一颗子树选多少(j为多少)。

可以滚动数组+倒叙循环把空间去一维

问题#

子树选的数目不能等于q，否则这颗子树的根节点就选不了了，导致后代所有的课都选不了（行48）

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
int read()
6
{
7
  int f = 1, x = 0;
8
  char ch = getchar();
9
  while(ch < '0' || ch > '9')
10
  {
11
    if(ch == '-') f = -1;
12
    ch = getchar();
13
  }
14

15
  while(ch >= '0' && ch <= '9')
16
  {
17
    x = x * 10 + ch - '0';
18
    ch = getchar();
19
  }
20
  return f * x;
21
}
22

23
const int N = 310;
24

25
int n, m;
26

27
int s[N], size[N];
28

29
int head[N], nxt[N], to[N], cnt = 1;
30

31
int f[N][N];//表示以u为子树中选m个学科最多能获得多少学分
32

33
void add(int x, int y)
34
{
35
  nxt[++cnt] = head[x];
36
  to[cnt] = y;
37
  head[x] = cnt;
38
}
39

40
void dfs(int u)
41
{
42
  for(int i = head[u]; i; i = nxt[i])
43
  {
44
    int v = to[i];
45
    dfs(v);
46
    for(int q = m;q >= 0;q--)
47
    {
48
      for(int k = 0;k < q/*子树选的数目不能等于q，否则这颗子树的根节点就选不了了，导致后代所有的课都选不了*/;k++)
49
      {
50
        f[u][q] = max(f[u][q], f[v][k] + f[u][q - k]);
51
      }
52
    }
53
  }
54
}
55

56
int main()
57
{
58
  n = read(), m = read() + 1;
59

60
  int anc;
61

62
  for(int i = 1;i <= n;i++)
63
  {
64
    anc = read();
65
    s[i] = read();
66
    add(anc, i);
67
    f[i][1] = s[i];
68
  }
69
  dfs(0);
70
  cout << f[0][m];
71
}