题解 P2014 【选课】
ouuan
2018-11-21 22:12:52
这里提供一种 $O(nm)$ 的解法，来自国家集训队论文《徐持衡〈浅谈几类背包题〉》。之前有几篇题解也是这个做法，但都没有详细的讲解。
可以在我出的[【数据加强版】选课](https://www.luogu.org/problemnew/show/U53204) 测试 $O(nm)$ 做法。
> 注：本文中以 $a_i$ 代指题面中的学分 $s_i$。
## 一、$O(nm^2)$ 做法
先说一下 $O(nm^2)$ 的做法，以便后文讲解。
用 $f_{i,j}$ 表示以 $i$ 为根的子树中选 $j$ 门课能获得的最大学分，转移时先处理子树，再利用背包对子树的答案进行合并。
如果把每个子树都看作一个物品，这个物品的价值随它的体积而变（即论文中所述的“泛化物品”），体积即选择课的门数，价值即获得的学分，对于一颗子树 $s$ ，选择 $k$ 门课时能获得的学分为 $f_{s,k}$ ，$f_{s,k}$ 即物品 $s$ 在体积为 $k$ 时的价值。
合并某一棵子树的答案，也就是将“已经合并好的部分”与“一颗子树”这两个物品进行合并，**由于你可以在两棵不同的子树中各选一些课**，所以需要枚举两个物品各自的体积来进行合并。合并复杂度为 $O(m^2)$
具体的实现可以看其它题解。
## 二、$O(nm)$ 做法
上文中提到，导致复杂度增大的关键就在于“**你可以在两棵不同的子树中各选一些课**”。如果要么选择“已经合并好的部分”，要么选择当前这棵子树，合并答案时只用对两个物品的价值取max即可。
考虑将“‘已经合并好的部分’加上节点 $s$”赋给子树 $s$ 作为初始值（$f_{i,j-1}+a_s\rightarrow f_{s,j}$），那么 $f_{i,j}$ 的含义变为了：在已经处理过的所有节点中选择 $j$ 个节点，并且必须选择 $i$ 节点的答案。
设节点 $i$ 的深度为 $dep$，那么选择 $i$ 就必须选择 $i$ 到树根的链上的 $dep$ 个节点，所以更新答案时，$f_{i,j}(j\le dep)$ 不会更新。
由于 $f_s$ 的物品集包含了 $f_i$ 的物品集，$f_s$ 和 $f_i$ 所表示的选择实际上是没有交集的，分别是 “在已经处理了的所有节点中选 $s$ 节点的所有方案” 和 “在已经处理了的所有节点中不选 $s$ 的所有方案”。
因此，合并子树的答案时，不能从“已经合并好的部分”和“一颗子树”中各取一部分体积，而只能两者选其一（本质上是选/不选这棵子树的根节点），所以合并就是 $O(m)$ 的。
参考代码：
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
void dfs(int u,int dep);
void add(int u,int v);
const int N=310;
int head[N],nxt[N],to[N],cnt;
int n,m,a[N],f[N][N];
int main()
{
int i,k;
scanf("%d%d",&n,&m);
for (i=1;i<=n;++i)
{
scanf("%d%d",&k,a+i);
add(k,i);
}
dfs(0,0); //按理来说应该将f[0][j]全部赋为a[0]，然后dfs(0,1)，但由于0是虚的根节点，就不需要这样做了。
printf("%d",f[0][m]); //答案是f[0][m]而非f[0][m+1]的原因同上
return 0;
}
void add(int u,int v)
{
nxt[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
}
void dfs(int u,int dep)
{
int i,j,v;
for (i=head[u];i;i=nxt[i])
{
v=to[i];
for (j=dep+1;j<=m;++j)
{
f[v][j]=f[u][j-1]+a[v];
}
dfs(v,dep+1);
for (j=dep+1;j<=m;++j)
{
f[u][j]=max(f[u][j],f[v][j]);
}
}
}
```
## 三、其它的 $O(nm)$ 做法
[dfs序dp](https://zryabc.blog.luogu.org/luo-gu-p2014-xuan-ke-xian-xu-bian-li-you-hua-shu-xing-bei-bao-post)
[多叉树转二叉树](https://www.luogu.org/blog/user9168/solution-p2014)，因为是p没仔细看具体做法...
[上下界优化](https://ouuan.github.io/%E6%A0%91%E4%B8%8A%E8%83%8C%E5%8C%85%E7%9A%84%E4%B8%8A%E4%B8%8B%E7%95%8C%E4%BC%98%E5%8C%96/)