Doing Homework

题意：
一行给出科目名称，截止时间，需要的时间，超出截止时间多久就扣多少分，求一个做作业的顺序使扣的分最少，并按字典序打印顺序。科目的名称是按字典序给出的

思路：
状压入门
二进制位表示一个数有没有被取

指的是已做作业结合的上一个集合，指由上一个集合到集合做的是什么作业，表示到集合已经过了多久，就是做了集合的作业会扣的最少的分。

一个细节点是，每次优先遍历字典序大的作业去得到的状态，这样保证前面选择的作业字典序最小

Code：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
using namespace std;
typedef long long ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
string s[15];
int d[15],need[15];
struct node{
    int pos,last,now,cost;
}dp[1<<15];
void print(int x) {
    if(!x) return;
    print(dp[x].last);
    cout<<s[dp[x].pos]<<endl;
}
int main() {
    int t=read(),n;
    while(t--) {
        n=read();
        for(int i=0;i<n;++i) {
            cin>>s[i];
            d[i]=read(),need[i]=read();
        }
        dp[0].last=dp[0].now=0;
        for(int i=1,last,tmp,l;i<(1<<n);++i) {
            dp[i].cost=0x3f3f3f3f;
            for(int j=n-1;j>=0;--j) {
                l=1<<j;
                if(i&l) {
                    last=i-l;
                    tmp=dp[last].now+need[j]-d[j];
                    if(tmp<0) tmp=0;
                    if(tmp+dp[last].cost<dp[i].cost) {
                        dp[i].cost=dp[last].cost+tmp;
                        dp[i].last=last;
                        dp[i].now=dp[last].now+need[j];
                        dp[i].pos=j;
                    }
                }
            }
        }
        printf("%d\n",dp[(1<<n)-1].cost);
        print((1<<n)-1);
    }
    return 0;
}