首先是原题的题解:
显然先修结构是森林, 设一个超级根, 作为所有没有先修课节点的先修课, 价值为 0, 然后在这颗超级树里选 m+1 个答案, 就是原题的答案。
设 fu,i 表示在以 u 为根的子树里选 i 门课的最大得分, 那么:
[sf f_{u,i} = max_{vin som(u),sum k_v = i-1} {sum f_{v,k_v}} + a_u
]
这个可以通过背包合并子树, 然后移位即可。
合并子树 u,v:
[sf f_{u,i} = max_k{f_{u,i-k}+f_{v,k}}
]
#include<bits/stdc++.h>
using namespace std;
const int N = 303;
int n, m, a[N];
vector<int> e[N];
int f[N][N];
void dfs(int u) {
for(vector<int>::iterator it = e[u].begin(); it != e[u].end(); ++it) {
int v = *it;
dfs(v);
for(int j = m; j >= 1; --j)
for(int k = 0; k <= j; ++k)
f[u][j] = max(f[u][j], f[u][k] + f[v][j-k]);
}
for(int i = m+1; i >= 1; --i) f[u][i] = f[u][i-1] + a[u];
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) {
int p;
scanf("%d%d", &p, &a[i]);
e[p ? p : n+1].push_back(i);
}
dfs(n+1);
cout << f[n+1][m+1];
return 0;
}
上下界优化:
void dfs(int u) {
siz[u] = 1;
for(vector<int>::iterator it = e[u].begin(); it != e[u].end(); ++it) {
int v = *it;
dfs(v);
for(int j = min(m, siz[u]+siz[v]); j >= 1; --j)
for(int k = max(0,j-siz[u]); k <= j && k <= siz[v]; ++k)
f[u][j] = max(f[u][j], f[u][j-k] + f[v][k]);
siz[u] += siz[v];
}
for(int i = m+1; i >= 1; --i) f[u][i] = f[u][i-1] + a[u];
}
优化后的总复杂度是 O(n2) 的。