HDOJ1074 状态压缩DP

这道题是我第一次接触状态压缩dp，记录下来留个纪念吧。

http://acm.hdu.edu.cn/showproblem.php?pid=1074

给定一个算法问题如下：读取T个测试用例。对于每个测试用例，在第一行读取一个整数N代表学科数目。随后的N行分别包含三门学科的信息：学科名称、完成作业的时间截止日期以及完成这门学科作业所需的天数。当某一学科的作业完成时间超过截止日期时会产生相应的分数扣减（每超过一天则扣相应分数）。需要注意的是，在所有测试用例中，请将各学科名称按照字母顺序依次给出名称。我们的任务是设计一个算法找出最优的作业处理顺序以使得总分数最少（如果有多个最优解，则选择字典序最小的那个）。

首先的一个主要思路就是，在这道题中我们需要明确各个课程的状态定义方式——哪些课程已经完成作业而哪些课程还未完成作业。然而这种表示方式却相当繁琐。于是我们考虑采用一种称为"状态压缩"的技术来简化这一过程。例如共有五门课程编号为A_0到A_4。每个课程对应一位二进制数位：其中A_i=0表示该课程尚未完成作业而A_i=1则表示该课程已完成作业。这样一来我们的目标就转化为：从初始状态A_0=A_1=A_2=A_3=A_4= \texttt{未完成}（即二进制形式为\texttt{全零}）到最终目标态\texttt{全一}最少需要扣除多少分？

其状态的到达存在五种可能性：第一种情况为从11110状态完成学科0之后转移；第二种情况是从11101状态完成学科1之后转移；第三种情况是从Q_2=...=Q_n=0的状态转移而来；第四种情况是从Q_2=...=Q_{n-2}=0, Q_{n-2}=...=Q_n=0}的状态转移而来；第五种情况是从全零态直接进入全一态的状态转移过程。我们依次计算所有可能路径下的最低扣分总和。