题意
有n个任务，每个任务有一个截止时间，超过截止时间一天，要扣一个分。
求如何安排任务，使得扣的分数最少。
解题
n个任务，共有n！种执行方式。因为n不超过15，所以用状态压缩的方式来表示状态（即二进制）。
设dp[s]表示以状态s作为终止状态的安排方式的所扣最少分数。
状态转移方程：dp[s]=min{dp[s],dp[last]+执行x任务所需时间}，状态last与s差了一个任务x。
因为要求在所扣分数相同的情况下，输出字典序最小的方案。所以，枚举状态last（通过枚举任务x来实现）需要排序枚举x任务。
AC代码
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <stack>
#define INF 0x3f3f3f3f
using namespace std;const int maxn=20;
struct node
{string str;int ed,t;node(string str,int ed,int t):str(str),ed(ed),t(t){}node(){}
}a[maxn];
struct state
{int sum;//已扣分数int time;//当前时间int pre;//上一个状态int key;
}b[1<<maxn];int main()
{int T;cin>>T;while(T--){int n,cnt=0;cin>>n;for(int i=0;i<n;i++){string str;int ed,t;cin>>str>>ed>>t;a[cnt++]=node(str,ed,t);}int tar=(1<<n)-1;for(int s=1;s<=tar;s++){b[s].sum=INF;for(int i=n-1;i>=0;i--)//因为时间相等，按任务名字字典序排序{int tmp=1<<i;b[tmp].pre=0;b[tmp].key=i;if(s&tmp){int last=s-tmp;int add=b[last].time+a[i].t-a[i].ed;if(add<0) add=0;if(add+b[last].sum<b[s].sum){b[s].sum=add+b[last].sum;b[s].pre=last;b[s].key=i;b[s].time=b[last].time+a[i].t;}}}}int x=tar;cout<<b[tar].sum<<endl;stack<string> sta;while(x){int k=b[x].key;sta.push(a[k].str);x=b[x].pre;}while(!sta.empty()){cout<<sta.top()<<endl;sta.pop();}}return 0;
}