题目链接：https://vjudge.net/problem/HDU-1074
n<=15，很明显是状压dp,令f[i][j]表示在状态i下最后一位是j的最小代价（状态i的第j位一定为1）f[i][j]一定是从状态（i-(1<<(k-1)))中转移过来的，至于上一个状态以谁结尾是最小值还需要判断，我是在更新当前状态时就判断一下那个最小，因为点的标号从1开始，那下标0的数组就没有用到就用它来保存该状态下的最小值，计算最小代价，你首先需要知道完成当前状态需要花费的时间才能计算代价，所以又多开一维，f[i][j][0]表示完成当前状态的时间（这个与顺序是无关的）
f[i][j][1]还是最小代价
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=16;
int t,n,m,a[N],b[N],ans;
map<int,string> mp;
vector<int> res;
int f[1<<N][N][2];
void dfs(int s)
{
if(!s) return ;
int l=0x3f3f3f3f,r;
for(int i=n;i;i--)//找当前状态下的最小值，输出要求字典序最小，从后向前推的，相同代价下使后面的数大因为是一个全排列自然整体的字典序就小了
{
if(f[s][i][1]<l)
{
l=f[s][i][1];
r=i;
}
}
res.push_back(r);
dfs(s-(1<<(r-1)));
}
int main()
{
cin>>t;
while(t--)
{
memset(f,0x3f,sizeof f);
cin>>n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s>>a[i]>>b[i];
mp[i]=s;
}
f[0][0][0]=f[0][0][1]=0;
for(int i=1;i<(1<<n);i++)
{
int l=-1,r;//l当前状态最小代价的那个点，r最小代价
for(int k=1;k<=n;k++)
{
if((i&(1<<(k-1)))&&f[i-(1<<(k-1))][0][0]!=0x3f3f3f3f)
{
int v=f[i-(1<<(k-1))][0][0];//前一个状态最小代价的那个点
f[i][k][0]=f[i-(1<<(k-1))][v][0]+b[k];//当前状态的完成时间
f[i][k][1]=min(f[i][k][1],f[i-(1<<(k-1))][v][1]+max(0,f[i][k][0]-a[k]));//最小代价=前几个点的最小代价之和加当前点的代价
if(l==-1||f[i][k][1]<r) //更新当前状态最小代价
{
l=k;
r=f[i][k][1];
}
}
}
if(l!=-1)//保存当前状态最小代价，l=-1就是当前状态行不通，貌似没用到
f[i][0][0]=l;
}
dfs((1<<n)-1);//递推求顺序
cout<<f[(1<<n)-1][res[0]][1]<<endl;
for(int i=n-1;i>=0;i--)
cout<<mp[res[i]]<<endl;
res.clear();
}
return 0;
}