[CTSC1997]选课

题面

题解

树形背包板子题。

设(f[i][j])表示在以(x)为根的子树选(j)门课（包括(x)）能够获得的最高学分，用分组背包转移即可。

代码

复制代码#include<cstdio> #include<vector> #define RG register inline int read() { int data = 0, w = 1; char ch = getchar(); while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if(ch == '-') w = -1, ch = getchar(); while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar(); return data*w; } const int maxn(310); std::vector<int> g[maxn]; typedef std::vector<int>::iterator iter; int s[maxn], f[maxn][maxn], n, m; void dfs(int x) { f[x][0] = 0; for(RG iter it = g[x].begin(); it != g[x].end(); ++it) { int to = *it; dfs(to); for(RG int v = m + 1; v; --v) for(RG int j = 0; j < v; ++j) f[x][v] = std::max(f[x][v], f[x][v - j] + f[to][j]); } } int main() { n = read(); m = read(); for(RG int i = 1; i <= n; i++) g[read()].push_back(i), f[i][1] = s[i] = read(); dfs(0); printf("%dn", f[0][m + 1]); return 0; }

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
#include<cstdio>
#include<vector>
#define RG register
inline int read()
{
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data*w;
}
const int maxn(310);
std::vector<int> g[maxn];
typedef std::vector<int>::iterator iter;
int s[maxn], f[maxn][maxn], n, m;
void dfs(int x)
{
f[x][0] = 0;
for(RG iter it = g[x].begin(); it != g[x].end(); ++it)
{
int to = *it; dfs(to);
for(RG int v = m + 1; v; --v)
for(RG int j = 0; j < v; ++j)
f[x][v] = std::max(f[x][v], f[x][v - j] + f[to][j]);
}
}
int main()
{
n = read(); m = read();
for(RG int i = 1; i <= n; i++)
g[read()].push_back(i), f[i][1] = s[i] = read();
dfs(0); printf("%dn", f[0][m + 1]);
return 0;
}