程序设计思维与实践 Week12 作业 E 选做题 - 2

马上假期就要结束了，zjm还有 n 个作业，完成某个作业需要一定的时间，而且每个作业有一个截止时间，若超过截止时间，一天就要扣一分。
zjm想知道如何安排做作业，使得扣的分数最少。
Tips: 如果开始做某个作业，就必须把这个作业做完了，才能做下一个作业。

有多组测试数据。第一行一个整数表示测试数据的组数
第一行一个整数 n(1<=n<=15)
接下来n行，每行一个字符串(长度不超过100) S 表示任务的名称和两个整数 D 和 C，分别表示任务的截止时间和完成任务需要的天数。
这 n 个任务是按照字符串的字典序从小到大给出。

每组测试数据，输出最少扣的分数，并输出完成作业的方案，如果有多个方案，输出字典序最小的一个。

状态压缩dp，f表示当前状态最少扣的分数。暴力枚举每一种情况。然后枚举所有的作业，若某作业包含在当前情况中，则计算出当前作业被扣除的分数，更新当前状态的最小值，同时记录前驱，最后递归输出。由于需要字典序最小，因此逆序枚举作业，从而避免了排序。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxx=1e9;
int n,f[1<<16],pre[1<<16],sum[1<<16];
struct node
{
  string cla;
  int d;
  int c;
}a[16];
void output(int x)
{
  if(x==0) return;
  output(x-(1<<pre[x]));
  cout<<a[pre[x]].cla<<endl;
}
int main()
{
  int T;
  cin>>T;
  while(T--)
  {
    memset(f,0,sizeof(f));
    memset(pre,0,sizeof(pre));
    memset(sum,0,sizeof(sum));
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i].cla>>a[i].d>>a[i].c;
    int tot=(1<<n);
    for(int i=1;i<=tot;i++)
    {
      f[i]=maxx;
      for(int j=n-1;j>=0;j--)
      {
        int now=1<<j;
        if(!(i&now)) continue;
        int tmp=sum[i-now]+a[j].c-a[j].d;
        tmp=max(0,tmp);
        if(f[i]>f[i-now]+tmp)
        {
                    f[i]=f[i-now]+tmp;
                    sum[i]=sum[i-now]+a[j].c;
                    pre[i]=j;
                }
      }
    }
    cout<<f[tot-1]<<endl;
    output(tot-1);
  }
  return 0;
}