题意：给你N（<=15）个作业，每个作业有最晚提交时间与需要做的时间，每次只能做一个作业，每个作业超出最晚提交时间一天扣一分
求出扣的最小分数，并输出做作业的顺序。如果有多个最小分数一样的话，则按照作业字典序输出（注意：输入也是按照字典序输入的）
题解：首先想到的是暴力dfs，但是会超时。接着我们看到n最大只有15，因此可以使用状压dp，但是状态不能用位置表示
但我们可以这样：0表示此作业没有做过，1表示已经用过了，接着遍历0->(1<<n)-1贪心（例如：3（011）可以找2（010）或者1（001）来计算）计算就好了，注意保存路径与字典序输出
注意我们要使用状压dp需要找到一个只有两种状态的事件
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<30; const ll INF=1ll<<60; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=2<<16;//压缩成现在处理过（1）与没处理过（0） const int Max2=150; char str[20][Max2]; int deal[Max2],val[Max2],vis[Max]; int dp[2][Max];//一位记录之前有几天 一位记录最小降低分数 void DP(int n) { dp[0][0]=dp[1][0]=0;//全没处理过 vis[0]=0; int temp; for(int i=1;i<(1<<n);++i) { dp[1][i]=Inf; temp=i; for(int j=0;j<n;++j) { int tmp=1<<j; if((temp|tmp)==temp)//第j位有1 { int minx=dp[1][i-tmp]+max(0,val[j]+dp[0][i-tmp]-deal[j]); if(minx<=dp[1][i]) { dp[1][i]=minx; dp[0][i]=dp[0][i-tmp]+val[j]; vis[i]=i-tmp; } } } } return; } int Lowday(int m) { for(int i=0;;m>>=1,++i) if(!m) return i-1; } void dfs(int now,int pre) { if(!now) { printf("%s ",str[Lowday(pre)]); return; } dfs(vis[now],now); printf("%s ",str[Lowday(pre-now)]); return; } int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;++i) { scanf("%s %d %d",str[i],&deal[i],&val[i]); } DP(n); printf("%d ",dp[1][(1<<n)-1]); dfs(vis[(1<<n)-1],(1<<n)-1); } return 0; }