DP類的狀態壓縮。這題其實就是求所有家庭作業的全排列，也就是最多有15！種放法，而 15！=1 307 674 368 00 所以暴力肯定會超時的。
這題的模型就是類似於數塔一樣的。同時由於狀態太多。所以利用二進制狀態壓縮。
下面是AC代碼 ：
[cpp]
#include<iostream>
#include<string>
#include<stack>
using namespace std;
struct node{
string name;
int d; //截止日期
int c; //需要花費日期
}hw[20];
struct point{
int now,pre; //當前狀態id,與過去狀態id
int now_time; //當前時間
int score; //當前最少花費
int key; //當前課程的id
}dp[40000];
int main(){
int t,n,i,j;
cin>>t;
while(t--){
cin>>n;
for(i=0;i<n;i++) cin>>hw[i].name>>hw[i].d>>hw[i].c;
dp[0].now_time=0; dp[0].score=0; dp[0].now=0;
for(i=1;i<(1<<(n));i++){
dp[i].score=1000000000;
for(j=n-1;j>=0;j--){
if(i&(1<<j)){
int pre_id=i-(1<<j),temp=0;
if(dp[pre_id].now_time+hw[j].c>hw[j].d)
temp=dp[pre_id].now_time+hw[j].c-hw[j].d;
else temp=0;
if(dp[pre_id].score+temp<dp[i].score){
dp[i].score=dp[pre_id].score+temp;
dp[i].now=i;
dp[i].pre=pre_id;
dp[i].now_time = dp[pre_id].now_time+hw[j].c;
dp[i].key=j;
}
}
}
}
stack<string >st;
cout<<dp[(1<<n)-1].score<<endl;
int t=(1<<(n))-1;
while(dp[t].now!=0){
st.push(hw[dp[t].key].name);
t=dp[t].pre;
// cout<<t<<endl;
}
while(!st.empty()){
cout<<st.top()<<endl;
st.pop();
}
}
return 0;
}
