タイトル#
[CTSC1997] 選択科目#
タイトルの説明#
大学では、各学生は一定の単位を取得するために、多くの科目からいくつかの科目を選んで学ぶ必要があります。いくつかの科目は、他の科目の前に学ぶ必要があります。例えば、線形代数は常に他の科目の前に学ぶ必要があります。現在、$N$ の科目があり、各科目には単位があり、各科目には 1 つまたはそれ以上の直接の前提科目があります（もし科目 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 はいくつか）。
配列をロールして逆順にループすることで、空間を 1 次元にできます。
問題#
部分木で選ぶ数は q と等しくなってはいけません。そうでないと、この部分木の根ノードは選べなくなり、その後のすべての科目を選べなくなります（行 48）。
コード#
#include<bits/stdc++.h>
using namespace std;
int read()
{
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
const int N = 310;
int n, m;
int s[N], size[N];
int head[N], nxt[N], to[N], cnt = 1;
int f[N][N];//uを根とする部分木からm個の科目を選ぶことで得られる最大の単位数を表します
void add(int x, int y)
{
nxt[++cnt] = head[x];
to[cnt] = y;
head[x] = cnt;
}
void dfs(int u)
{
for(int i = head[u]; i; i = nxt[i])
{
int v = to[i];
dfs(v);
for(int q = m;q >= 0;q--)
{
for(int k = 0;k < q/*部分木で選ぶ数はqと等しくなってはいけません。そうでないと、この部分木の根ノードは選べなくなり、その後のすべての科目を選べなくなります*/;k++)
{
f[u][q] = max(f[u][q], f[v][k] + f[u][q - k]);
}
}
}
}
int main()
{
n = read(), m = read() + 1;
int anc;
for(int i = 1;i <= n;i++)
{
anc = read();
s[i] = read();
add(anc, i);
f[i][1] = s[i];
}
dfs(0);
cout << f[0][m];
}