本题改编自《数据结构与算法专题实验》第10–11页实验六。OJ: * 学期教学计划 - 题目详情 - Endermite OJ

一道典型的状态压缩dp题目. 题目如下:

学期教学计划-题目

一个专业有 n 门课程和 s 个学期。课程各占一个学期，每门课程有正整数学分；每学期总学分不能超过 c。所有直接先修课程都必须在本课程之前的学期完成。

给定一种策略，输出任意一个最优教学计划：

  • B（均匀）：令第 i 学期的总学分为 L_i，最小化 L_1²+...+L_s²。
  • F（前置）：最大化向量 (L_1,...,L_s) 的字典序。即先尽量增加第1学期学分；第1学期相同时再比较第2学期，以此类推。

空学期的学分为0，两个策略均允许空学期。每门课程必须且只能安排一次。

从 curriculum.in 读取输入，将答案写入 curriculum.out。

输入格式

第一行是 n s c mode，mode 是 B 或 F。

随后 n 行，第 i 行为：

id_i credit_i k_i pre_1 ... pre_k

课程号是恰好3位ASCII字母或数字组成的字符串，区分大小写；n 个课程号互不相同。k_i 是本课程的直接先修课程数，同一行的先修号不重复。先修号可能没有对应课程，此时应报告 INVALID。若存在未知先修号，无论其它条件如何均输出 INVALID。

输出

若存在未知先修号，输出 INVALID。

否则，若不存在满足学分和先修条件的计划，输出 IMPOSSIBLE。先修关系有环、自身先修、单课学分超过上限等均可能导致无解。

否则，第一行输出 OK；第二行输出 n 个整数，依次表示输入中各门课程安排的学期，编号为 1..s。存在多个最优计划时输出任意一个，评测器会验证可行性及所选策略的最优性。

范围

1 ≤ n ≤ 12，1 ≤ s ≤ 12，1 ≤ c ≤ 100，1 ≤ credit_i ≤ 100，0 ≤ k_i ≤ 12。

样例

输入数据 1

3 3 5 B
A01 2 0
B02 3 0
C03 2 1 A01

输出数据 1

OK
1 2 3

该计划的学期学分为 (2,3,2)，平方和为17，达到最小值。1 3 2 也是合法最优答案。

相比原题的改进

  • 目标更明确。 原题要求“尽量均匀”和“尽可能集中在前几个学期”，本题分别用学分平方和最小、学分向量字典序最大来定义，使方案优劣有明确的比较标准。
  • 更便于自动评测。 统一输入输出格式，明确 INVALID 与 IMPOSSIBLE 的含义和优先级，并接受任意最优计划，兼顾判定的一致性与答案的多样性。
  • 更聚焦精确优化。 将原题建议的课程数小于 100 收紧为不超过 12，便于用状态压缩 DP 求出全局最优，突出建模与最优性分析，更适合作为算法训练题。

样例解读

总学分为 \(7\)，分到三个学期时，整数意义下最均匀的分配是 \(2,2,3\)，因此平方和不可能小于 \(17\)。上述安排满足先修关系和学分上限，所以达到最优值。

如果只把样例的策略改为 F，则可以在第 1 学期修 A01 和 B02，第 2 学期修 C03，得到 \((5,2,0)\)。第 1 学期已达到上限 \(5\)，剩下的 \(2\) 学分也尽早完成，因而这是前置策略下的最优方案。

B 均匀策略与 F 前置策略对比：学期学分分别为 2、3、2 和 5、2、0。

Go 的文件输入输出

实验题使用文件输入输出。下面分别说明文件的打开与关闭、缓冲读写器的创建，以及输入输出函数的使用。

打开输入、输出文件，并用 defer 安排函数返回前的资源处理：

in, err := os.Open("curriculum.in")
if err != nil {
	panic(err)
}
out, err := os.Create("curriculum.out")
if err != nil {
	panic(err)
}
defer in.Close()
defer out.Close()
defer writer.Flush()

defer 会在当前函数返回前执行，多个 defer 按后注册、先执行的顺序调用。因此，退出时依次执行 writer.Flush()、out.Close()、in.Close()：先把缓冲区中尚未写出的内容提交给输出文件，再关闭文件。

缓冲读写器由下面两行创建。组合这些片段时，将它们放在 defer writer.Flush() 之前；文末完整代码展示了相应顺序。

reader := bufio.NewReader(in)
writer := bufio.NewWriter(out)

fmt.Fscan 和 fmt.Fprint 系列函数通过第一个参数指定输入来源或输出目标。这里传入 reader 或 writer，例如：

fmt.Fscan(reader, &n, &s, &c, &mode)

用位掩码表示课程集合

动态规划需要记录“已经修完哪些课”。每门课只有已修和未修两种状态，正好可以用一个二进制位表示。

我们按输入顺序给课程编号 \(0,1,\ldots,n-1\)，用整数 mask 的第 \(j\) 位表示第 \(j\) 门课程是否已修：

  • 第 \(j\) 位为 1：已修。
  • 第 \(j\) 位为 0：未修。

位编号从最低位开始，第 0 位位于二进制表示的最右侧。 例如，样例中的 A01、B02、C03 分别对应第 0、1、2 位，mask = 0b011 就表示已经修完 A01 和 B02。

课程与二进制位的对应：011 表示 A01、B02 已修，C03 未修。

位运算可以直接完成集合操作：按位与用于检查某一位，按位或用于将指定位置为 1，Go 的按位清除运算符 &^ 则可将指定位置为 0。

总共有 \(2^n\) 种课程集合。即使 \(n=12\)，也只有 \(4096\) 种状态，适合直接作为 DP 数组的下标。空集为 0；完整代码中用 total 表示状态总数，用 fullMask 表示全部课程组成的集合。

输入与预处理

先读课程，再解析先修关系

课程号是字符串，位运算需要整数编号，因此用 map[string]int 建立课程号到输入下标的映射。

这里需要分两步处理：读入时保存先修课程号，所有课程读完后，再把先修课程号转换为位掩码。 因为一门课的先修课程可能出现在输入的后面，不能在读到它时就判断课程号是否未知。

idMap := make(map[string]int)
ids := make([]string, n)
credits := make([]int, n)
preMask := make([]int, n)
preIds := make([][]string, n)
for i := 0; i < n; i++ {
	fmt.Fscan(reader, &ids[i], &credits[i], &preCount)
	idMap[ids[i]] = i
	preMask[i] = 0
	for j := 0; j < preCount; j++ {
		var tempPreCourse string
		fmt.Fscan(reader, &tempPreCourse)
		preIds[i] = append(preIds[i], tempPreCourse)
	}
}

用 preMask[i] 表示第 \(i\) 门课程的直接先修课程集合。如果它要求先修第 \(j\) 门课程，就将第 \(j\) 位置为 1：

// Mask init
for i := 0; i < n; i++ {
	for _, preId := range preIds[i] {
		index, ok := idMap[preId]
		if !ok {
			fmt.Fprintln(writer, "INVALID")
			return
		}
		preMask[i] |= 1 << index
	}
}

样例中只有 C03 有先修课，因此 preMask[2] = 0b001，其余两门课的先修掩码为 0。未知课程号在这一步统一处理，之后才判断计划是否可行，满足 INVALID 的优先级要求。

预计算每个集合的学分和

两种策略都需要反复计算“本学期选课集合的总学分”。可以提前枚举所有集合，将结果存入 creditsForMask：

total := 1 << n
creditsForMask := make([]int, total)
for mask := 0; mask < total; mask++ { //credits init
	for j := 0; j < n; j++ {
		if mask&(1<<j) != 0 {
			creditsForMask[mask] += credits[j]
		}
	}
}

预处理后，选课时可以直接查询集合的学分和。下文用 \(w(T)\) 表示集合 \(T\) 的学分和，即代码中的 creditsForMask[take]。

按学期进行动态规划

状态：前几个学期结束后，已经修完哪些课

两种策略共享相同的状态结构：

(i, mask) 表示前 \(i\) 个学期已经结束，恰好修完 mask 中的课程。

学期数 \(i\) 决定还剩多少时间，mask 决定哪些课程已经完成、哪些课程可以继续修。未来的可选课程只与这两项有关，不需要保存完整的历史排课过程。

初始状态为 (0, 0)，目标状态为 (s, fullMask)。同一个状态可能由多种排课方式到达；我们只保留其中目标值最优的一种。

转移：从可选课程中选出本学期的课程

在状态 (i, mask) 下，第 \(j\) 门课程能够安排到第 \(i+1\) 学期，当且仅当：

  1. 课程还没有修过：mask & (1 << j) == 0。
  2. 所有直接先修课程都已经修完：mask & preMask[j] == preMask[j]。

据此构造可选课程集合，代码中记为 availble：

availble := 0
for j := 0; j < n; j++ {
	bit := 1 << j
	if bit&mask == 0 && mask&preMask[j] == preMask[j] {
		//not learned and learned all pre lesson
		availble |= bit
	}
}

先修条件必须用上一学期结束后的 mask 判断。 本学期新选的课程不能立刻用来解锁另一门课，否则就会把先修课和后续课安排在同一学期。

状态转移示意：已修 A01，下一学期选 B02、C03 共 5 学分，修完全部课程。

注意，可选课程集合只包含满足先修条件的候选课程，学分总和可能超过上限。真正选取的 take 应是它的某个子集，并且满足 creditsForMask[take] <= c。

可以用下面的写法枚举这个集合的所有子集：

for take := availble; ; take = (take - 1) & availble {
	//here is your dp
	if take == 0 {
		break
	}
}

take - 1 将最低的一个 1 变为 0，并将其右侧的位变为 1；再与 availble 按位与，就只保留候选集合中的位。这样能按数值递减的顺序遍历所有子集。例如 availble = 0b110 时，枚举顺序是 110 → 100 → 010 → 000。

必须枚举空集 take = 0，因为题目允许空学期。处理完空集后要立即退出；否则 (0 - 1) & availble 又会回到 availble，造成循环。

B 策略：保存最小平方和

定义 dp[i][mask] 为到达状态 (i, mask) 时，前 \(i\) 个学期的学分平方和的最小值。初始值为：

$$ \mathrm{dp}[0][0]=0, $$

其余状态初始化为 INF，表示不可达。

选定合法的 take 后，令 nextMask = mask | take，状态转移为：

$$ \begin{aligned} &\mathrm{dp}[i+1][\text{nextMask}]\\ &=\min\bigl(\mathrm{dp}[i+1][\text{nextMask}],\\ &\qquad\mathrm{dp}[i][\text{mask}]+w(\text{take})^2\bigr). \end{aligned} $$

也就是在历史最优值的基础上，加上本学期总学分的平方。这里平方的是学分和，而不是把每门课的学分分别平方后相加。

只有目标值严格变优时才更新；目标值相同可以保留原方案，因为题目允许输出任意最优计划。

F 策略：保存字典序最大的学分向量

F 策略比较的是各学期的学分向量，而不是课程编号或课程顺序。因此，dp[i][mask] 保存到达该状态时，字典序最大的学分前缀 \((L_1,\ldots,L_i)\)。

由于最多有 12 个学期，代码使用 [12]int 保存向量。先把当前状态的向量复制到 candidate，再将本学期的学分写入 candidate[i]。向量下标从 0 开始，因此该位置对应第 \(i+1\) 学期。

Go 中数组赋值会复制整个数组，因此修改 candidate[i] 不会改动原状态。

比较候选向量与已有向量时，从前往后找到第一个不同的位置，该位置学分更大的方案更优。前面的学期一旦分出高下，后面的学期就不再影响比较结果。

向量全为零也可能是合法状态，例如前几个学期都为空，所以另外使用 reachable[i][mask] 标记状态是否可达。更新条件是：

  • 目标状态尚不可达；或
  • 目标状态可达，但候选向量的字典序更大。

不能只按“本学期学分最多”选定一组课程后就丢掉其他选择。不同选课集合会解锁不同的后续课程，仍需通过 mask 区分，并在最终能完成全部课程的方案中比较字典序。

为什么每个状态只保留一个最优值就够了

假设两种历史方案都到达 (i, mask)。它们剩余的学期数相同、已修课程相同，因此后续能采用的排课方案也相同。

  • 对 B 策略，两种历史方案接上同一后续方案，会增加相同的平方和。历史值较大的方案不可能反超。
  • 对 F 策略，若一个历史学分前缀的字典序更小，无论后面接上什么，都无法改变前面第一个不同位置的大小关系。

因此，可以舍弃同一状态下较差的历史方案。同时，算法枚举了每个状态下所有合法的选课子集，任何可行计划都能沿着相应转移到达终点，最优计划也不会遗漏。

判断可行性并还原方案

所有转移结束后，检查 (s, fullMask)：B 策略看其值是否仍为 INF，F 策略看 reachable 是否为 false。终点不可达就输出 IMPOSSIBLE。

这里不必单独写拓扑排序来判环。环中的课程无法满足“全部先修课程已在之前学期完成”，因此无法通过合法转移修完；自身先修同理。单课学分超限、学期数不足等情况，也会表现为终点不可达。

题目要求输出具体排课，因此每次更新最优值时，还需用 route[i+1][nextMask] 记录该学期选取的课程集合 take。

从 (s, fullMask) 开始倒推：读取本学期的 take，把其中各门课程的答案记为当前学期；然后从 mask 中移除这些课程，再继续回溯上一学期。

回溯时，take 一定是当前 mask 的子集，异或会将本学期所选课程对应的位清零，恢复上一学期的课程集合。若本学期为空，mask 保持不变，但学期编号仍减一，因此同样能正确回溯。

实现亮点

  • 全局字典序最优。 F 策略按已修课程集合保留最优学分前缀，兼顾后续可行性，避免逐学期贪心选课。
  • 约束与求解统一。 先修条件直接融入状态转移，环、自身先修和学期不足统一由终点不可达识别，空学期也能自然处理。
  • 减少无效枚举与重复计算。 只枚举可选课程的子集，并预存各集合的学分和。
  • 回溯记录紧凑。 route 只保存本学期的选课集合，通过异或即可恢复前驱状态。
  • 输入处理完整。 先读完课程再解析先修号，支持向后引用，并保证 INVALID 的判定优先级。
  • 候选状态互不影响。 利用 Go 定长数组的值复制语义，修改候选学分向量不会影响原状态。

AC代码

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in, err := os.Open("curriculum.in")
	if err != nil {
		panic(err)
	}
	defer in.Close()
	out, err := os.Create("curriculum.out")
	if err != nil {
		panic(err)
	}
	defer out.Close()
	reader := bufio.NewReader(in)
	writer := bufio.NewWriter(out)
	defer writer.Flush()
	var n, s, c, preCount int
	var mode string
	fmt.Fscan(reader, &n, &s, &c, &mode)
	idMap := make(map[string]int)
	ids := make([]string, n)
	credits := make([]int, n)
	preMask := make([]int, n)
	preIds := make([][]string, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &ids[i], &credits[i], &preCount)
		idMap[ids[i]] = i
		preMask[i] = 0
		for j := 0; j < preCount; j++ {
			var tempPreCourse string
			fmt.Fscan(reader, &tempPreCourse)
			preIds[i] = append(preIds[i], tempPreCourse)
		}
	}
	// Mask init
	for i := 0; i < n; i++ {
		for _, preId := range preIds[i] {
			index, ok := idMap[preId]
			if !ok {
				fmt.Fprintln(writer, "INVALID")
				return
			}
			preMask[i] |= 1 << index
		}
	}
	// Main
	if mode == "B" {
		total := 1 << n
		const INF = 1 << 30
		//dp init
		dp := make([][]int, s+1) // dp[i] stores information in semester i
		creditsForMask := make([]int, total)
		for mask := 0; mask < total; mask++ { //credits init
			for j := 0; j < n; j++ {
				if mask&(1<<j) != 0 {
					creditsForMask[mask] += credits[j]
				}
			}
		}
		for i := 0; i <= s; i++ {
			dp[i] = make([]int, total)
			for mask := 0; mask < total; mask++ {
				dp[i][mask] = INF
			}
		}
		// Route init
		route := make([][]int, s+1)
		for i := 0; i <= s; i++ {
			route[i] = make([]int, total)
		}
		dp[0][0] = 0 //begin
		for i := 0; i < s; i++ {
			for mask := 0; mask < total; mask++ {
				if dp[i][mask] == INF {
					continue //INF from last semester
				}
				availble := 0
				for j := 0; j < n; j++ {
					bit := 1 << j
					if bit&mask == 0 && mask&preMask[j] == preMask[j] {
						//not learned and learned all pre lesson
						availble |= bit
					}
				}
				for take := availble; ; take = (take - 1) & availble {
					nextMask := mask | take
					if creditsForMask[take] <= c {
						sum := creditsForMask[take] * creditsForMask[take]
						if dp[i+1][nextMask] > dp[i][mask]+sum {
							dp[i+1][nextMask] = dp[i][mask] + sum
							route[i+1][nextMask] = take
						}
						//dp[i+1][nextMask] = min(dp[i+1][nextMask], dp[i][mask]+creditsForMask[mask]*creditsForMask[mask])
					}
					if take == 0 {
						break
					}
				}
			}
		}
		fullMask := total - 1
		if dp[s][fullMask] == INF {
			fmt.Fprintln(writer, "IMPOSSIBLE")
			return
		}
		semesters := make([]int, n)
		mask := fullMask
		for i := s; i >= 1; i-- {
			take := route[i][mask]
			for j := 0; j < n; j++ {
				if take&(1<<j) != 0 {
					semesters[j] = i
				}
			}
			mask ^= take
		}
		//print Ans
		fmt.Fprintln(writer, "OK")
		for i := 0; i < n; i++ {
			fmt.Fprintf(writer, "%v ", semesters[i])
		}
	}
	if mode == "F" {
		total := 1 << n
		//init
		dp := make([][][12]int, s+1) // dp[i] stores information in semester i
		reachable := make([][]bool, s+1)
		route := make([][]int, s+1)
		creditsForMask := make([]int, total)
		for mask := 0; mask < total; mask++ { //credits init
			for j := 0; j < n; j++ {
				if mask&(1<<j) != 0 {
					creditsForMask[mask] += credits[j]
				}
			}
		}
		for i := 0; i <= s; i++ {
			dp[i] = make([][12]int, total)
			reachable[i] = make([]bool, total)
			route[i] = make([]int, total)
		}
		reachable[0][0] = true //begin
		for i := 0; i < s; i++ {
			for mask := 0; mask < total; mask++ {
				if !reachable[i][mask] {
					continue //unreachable from last semester
				}
				availble := 0
				for j := 0; j < n; j++ {
					bit := 1 << j
					if bit&mask == 0 && mask&preMask[j] == preMask[j] {
						//not learned and learned all pre lesson
						availble |= bit
					}
				}
				for take := availble; ; take = (take - 1) & availble {
					nextMask := mask | take
					if creditsForMask[take] <= c {
						nowBetter := false
						candidate := dp[i][mask]
						candidate[i] = creditsForMask[take]
						if reachable[i+1][nextMask] == false {
							//Need to record
							nowBetter = true
						} else {
							for k := 0; k <= i; k++ {
								if candidate[k] != dp[i+1][nextMask][k] {
									nowBetter = candidate[k] > dp[i+1][nextMask][k]
									break
								}
							}
						}
						if nowBetter {
							dp[i+1][nextMask] = candidate
							reachable[i+1][nextMask] = true
							route[i+1][nextMask] = take
						}
					}
					if take == 0 {
						break
					}
				}
			}
		}
		fullMask := total - 1
		if !reachable[s][fullMask] {
			fmt.Fprintln(writer, "IMPOSSIBLE")
			return
		}
		semesters := make([]int, n)
		mask := fullMask
		for i := s; i >= 1; i-- {
			take := route[i][mask]
			for j := 0; j < n; j++ {
				if take&(1<<j) != 0 {
					semesters[j] = i
				}
			}
			mask ^= take
		}
		//print Ans
		fmt.Fprintln(writer, "OK")
		for i := 0; i < n; i++ {
			fmt.Fprintf(writer, "%v ", semesters[i])
		}
	}
}