题意：有n门课，每门课有截止时间和完成所需的时间，如果超过规定时间完成，每超过一天就会扣1分，问怎样安排做作业的顺序才能使得所扣的分最小
思路：二进制表示。
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define clc(a,b) memset(a,b,sizeof(a))
const int MAXN=<<;
struct node
{
int cost;
int pre;
int reduced;
} dp[MAXN];
bool visited[MAXN];
struct course
{
int deadtime;
int cost;
char name[];
} course[];
void output(int status)
{
int curjob=dp[status].pre^status;
int curid=;
curjob>>=;
while(curjob)
{
curid++;
curjob>>=;
}
if(dp[status].pre!=)
{
output(dp[status].pre);
}
printf("%s\n",course[curid].name);
}
int main()
{
// freopen("in.txt","r",stdin);
int T,n;
int i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int upper=<<n;
int dayupper=;
for(i=; i<n; i++)
{
scanf("%s%d%d",&course[i].name,&course[i].deadtime,&course[i].cost);
dayupper+=course[i].cost;
}
memset(visited,false,sizeof(visited));
dp[].cost=;
dp[].pre=-;
dp[].reduced=;
visited[]=true;
int work;
int tupper=upper-;
for(j=; j<tupper; j++)
{
for(work=; work<n; work++)
{
int cur=<<work;
if((cur&j)==)
{
int curtemp=cur|j;
int day=dp[j].cost+course[work].cost;
dp[curtemp].cost=day;
int reduce=day-course[work].deadtime;
if(reduce<)reduce=;
reduce+=dp[j].reduced;
if(visited[curtemp])
{
if(reduce<dp[curtemp].reduced)
{
dp[curtemp].reduced=reduce;
dp[curtemp].pre=j;
}
}
else
{
visited[curtemp]=true;
dp[curtemp].reduced=reduce;
dp[curtemp].pre=j;
}
}
}
}
printf("%d\n",dp[tupper].reduced);
output(tupper);
}
}