题目描述：
现在有N个作业，每个作业有截止时间和做完该作业需要的时间，如果某个作业在其截止日期之后做完，则扣分，扣的分数等于拖延的时间，问如何调度这N个作业的先后顺序，使得扣的分最少（N<15），多组数据
思路：
- N=15，不能用N！，能用2^N
- 状态压缩，把每个作业写没写看成一位，这样就有2^N个状态
- 记忆化搜索：从全1的状态向前搜索，边界条件是全0的状态，搜的过程中更新每个状态的最小值
- 最后按状态数组的信息，回溯打印路径
总结：
虽然比HDU-1024简单了一丢丢，但是也折腾了很长时间。
起初想构造一个排列树（从空集开始搜，一直搜到全集），加上最优性剪枝，发现这样不是记忆化搜索（我还以为是），可以画个排列树看一看就发现了
只有从全集开始搜，可能有两条路径搜到同一个集合，这样才是记忆化搜索，也就是从全1搜到全0
如果转成递推也很容易，计算顺序就是先计算集合元素少的，再计算集合元素多的，外层循环应该是从1-N
这里因为懒就不在写递推了，等有时间回顾再写
记忆化搜索代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int N;
struct HomeWork
{
string name;
int deadLine, needTime;
}H[15];
struct Status //同一状态的时间是相同的,但是最小分数是需要被更新的
{
int time;
int minScore;
}Sta[1<<16]; //一共有1<<16种状态
bool vis[1 << 16];
Status dfs(int now)
{
if (vis[now]) return Sta[now];
Sta[now].minScore = INT_MAX;
vis[now] = 1;
//找now状态的前导状态
for (int i = 0; i < N; i++)
{
if (now & (1 << i)) //做完第i个作业到达now状态
{
Status lastSta = dfs(now - (1 << i));
int nowTime = lastSta.time + H[i].needTime;
int nowScore = lastSta.minScore + max(nowTime - H[i].deadLine, 0);
Sta[now].time = nowTime;
Sta[now].minScore = min(Sta[now].minScore, nowScore);
}
}
return Sta[now];
}
//判断状态A可否由状态B经过第i个作业转化过来
bool Judge(Status A, Status B, int i)
{
int Time = B.time + H[i].needTime;
int Score = B.minScore + max(Time - H[i].deadLine, 0);
return Time == A.time && Score == A.minScore;
}
void print(int now)
{
if (now == 0) return; //边界
//找now的前导状态,保证字典序逆着找
for (int i = N-1; i >=0; i--)
{
if (now & (1 << i) && Judge(Sta[now], Sta[now - (1 << i)], i))
{
print(now - (1 << i));
cout << H[i].name << endl;
break; //注意break
}
}
}
int main()
{
int T; cin >> T;
while (T--)
{
memset(Sta, 0, sizeof(Sta));
memset(vis, 0, sizeof(vis));
cin >> N;
//注意编号从0开始,因为要进行二进制运算
for (int i = 0; i < N; i++)
cin >> H[i].name >> H[i].deadLine >> H[i].needTime;
Sta[0] = { 0,0 }; //起始状态,一个作业都没做,递归边界
vis[0] = 1;
Status finalSta = dfs((1 << N) - 1);
cout << finalSta.minScore << endl;
print((1 << N) - 1);
}
}