HDU 1074 Doing Homework

正文索引 [隐藏]

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

题目翻译

有N个科目,每个科目有Deadline 和完成时间。每个科目每超过Deadline一天就会扣一分。
问如何安排,才能扣最少的分数。

题解

N很小只有15,所以我们想到状压DP,然后我们预处理出每种科目的组合完成所需要的时间finishedTime[now Subjects]
F[now Subjects + New Subject]  = min (F[now Subjects + New Subject], max(F[now subjects] + finishedTime[now Subjects] + time[new subject] – deadline[new subject], 0))
记录方案很好实现

代码