链接：https://vjudge.net/problem/OpenJ_Bailian-4149

思路：dp+状态压缩，首先最小扣分只跟选什么课程有关，一旦课程选定那么最小扣分也就选定了。所以状态压缩可以用二进制01;来表示是否选这门课。

代码：

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int t,n;

//记录课程的结束时间，需要花费的时间
struct homework{
string name;
    int d,c;
}hw[20];

//记录路径，最小扣分以及最后结束的天数，用于dp
struct node{
    int pre;
    int minscore;
    int last;
    int finishday;
}dp[(1<<16)+20];

//返回路径
vector<int> getpath(int status){
    vector<int> path;
    while(status){
        path.push_back(dp[status].last);
        status = dp[status].pre;
    }
    reverse(path.begin(),path.end());
    return path;
}

int main(){
    cin>>t;
    while(t--){
        cin>>n;
    char name[60];
    int d,c;
    for(int i=0;i<n;i++)
       cin>>hw[i].name>>hw[i].d>>hw[i].c;
        dp[0].finishday = 0;
        dp[0].minscore = 0;
        dp[0].pre = -1;
        int m = 1<<n;

    for(int i=1;i<m;++i){
        dp[i].minscore = 1<<30;
        for(int j=0;j<n;++j){
            if(i&(1<<j)){  //枚举最后一个做的课程是什么
                int pre = i - (1<<j); // 上一个课程
                int finishday = dp[pre].finishday + hw[j].c;
                int tmpscore = finishday - hw[j].d;
                if(tmpscore<0)tmpscore = 0;
                if(dp[i].minscore>dp[pre].minscore + tmpscore){
                    dp[i].minscore = dp[pre].minscore + tmpscore;
                    dp[i].pre = pre;
                    dp[i].finishday = finishday;
                    dp[i].last = j;
                }
                if(dp[i].minscore==dp[pre].minscore+tmpscore){
                    vector<int> p1 = getpath(dp[i].pre);
                    vector<int> p2 = getpath(pre);
                    if(p2<p1){
                        dp[i].pre = pre;
                        dp[i].finishday = finishday;
                        dp[i].last = j;
                    }
                }
            }
        }
        }
        cout<<dp[m-1].minscore<<endl;
        int status = m-1;
        vector<int> path = getpath(status);
        for(int i=0;i<path.size();i++)cout<<hw[path[i]].name<<endl;
    }
    return 0;
}