[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;
}