ouuan 的博客

ouuan 的博客

题解 P2014 【选课】

posted on 2018-11-21 22:12:52 | under 题解 |

这里提供一种 $O(nm)$ 的解法,来自国家集训队论文《徐持衡〈浅谈几类背包题〉》。之前有几篇题解也是这个做法,但都没有详细的讲解。

可以在我出的【数据加强版】选课 测试 $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)$ 的。

参考代码:

#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

多叉树转二叉树,因为是p没仔细看具体做法...

上下界优化