当前位置:首页 > 动态规划 > 树形DP > 正文
SSOJ2139选课
2485+

题目大意:有n门学分在1到11的课,可以选m门,但有些课有先修课,需要选了先修课才能选该门课,请问最多能获得多少学分?

【题目描述】

魔法学院实行学分制。每门课程都有一定的学分,学员只要选修了这门课并考核通过就能获得相应的学分。学员最后的学分是他选修的各门课的学分的总和。

每个学员都要选择规定数量的课程。其中有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其它的一些课程的基础上才能选修。例如,《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号,课号依次为1,2,3,……

例如表中1是2的先修课,即如果要选修2,则1必定已被选过。同样,如果要选修3,那么1和2都一定已被选修过。

学员不可能学完学院所开设的所有课程,因此必须在入学时选定自己要学的课程。每个学员可选课程的总数是给定的。现在请你找出一种选课方案,使得你能得到学分最多,并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。

【输入格式】

输入文件的第一行包括两个正整数M、N(中间用一个空格隔开)其中M表示待选课程总数(1≤M≤1000),N表示学员可以选的课程总数(1≤N≤M)。

以下M行每行代表一门课,课号依次为1,2,…,M。每行有两个数(用一个空格隔开),第一个数为这门课的先修课的课号(若不存在先修课则该项为0),第二个数为这门课的学分。学分是不超过10的正整数。

【输出格式】

输出文件第一行只有一个数,即实际所选课程的学分总数。以下N行每行有一个数,表示学员所选课程的课号。

【输入样例】

7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2

【输出格式】

13

解题思路

选课关系是一棵树,定义状态,会变的是课程编号(子树根)以及选课数量,那么我们就定义f[i][j]表示以i为根的子树选j门课的最大学分。

先考虑简单的情况,如果这是一颗二叉树,整棵树选m门课,那么根结点a必须要选,左右子树共选m-1门课,可以用卡特兰数进行地推,枚举左子树lc选i(0到m-1)门课,那么右子树rc选j=m-1-i门课,f[a][m] = max(f[lc][i] + f[rc][j] + 课程a的学分)。然而这并不是二叉树,一个根结点可能有k个儿子,也就是m-1门课分到k个子树,每个子树选多少门课呢?暴力搜索的话是NP难度的。

一个巧妙的做法,就是将多叉树转成二叉树,转成左儿子右兄弟的结构:如根结点只有1个儿子,那就放在lc位置;如果有两个儿子,那么1个放在lc位置,另外一个放在lc的rc位置;如果有多个儿子,那么1个放在lc位置,1个放在lc的rc位置,后面陆续放到rc的rc位置……

这样就可以枚举左右子树选多少门课了,需要注意的是,选左子树的话,根必选,否则根只是可选,因为选右子树,右子树是根的兄弟,兄弟不选也没关系。因此,转移关系是这样的:以a为根的子树选m门课,不选a的话,f[a][m] = f[rc][m],即m门课都在右子树选完;选a的话,左子树可以选i=0~m-1门课,右子树选j=m-i门课。

当然,这道题还可以在树上做分组背包,即一个容量为m的背包,最多能装多少学分呢?根结点的子树各自看成一个物品,要么装/选,要么不装/选。需要注意的是,对于一个子树,他可以选0到m-1门课,也就是说这个物品占用的空间可以不一样;但是,如果用了选a门课的子树,就不能同时选b门课的同一棵子树,也就是说这个背包的不同状态只能选一种。因此,应该先枚举分组,再枚举容量,最后枚举物品的各种状态,就能保证同一个容量,不会同时选了不同状态的物品。f[a][i] = f[b][j] + f[a][i-j],儿子更新父亲,a的容量为i,b占用j容量,那么a可以先装i-j的容量,再加上b装了b的容量的学分。

剪枝:枚举容量的时候,一个子树a如果只有k个结点,那么子树a最多选k门课,容量最大为k,超过k的可以不枚举。

程序实现

DFS后续遍历,树上做分组背包,并根据子树结点数缩小枚举范围实现剪枝,时间复杂度是$O(n^2)$,因为深搜每个结点a,循环次数为子树内任选两点的方案数,整个搜索的时间复杂度就是任意两点的方案数。

逆BFS序分组背包,儿子更新父亲:

左儿子右兄弟,枚举左右子树选课数量:

SSOJ2139选课:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!