本题数据范围较小,但暴力枚举的话肯定超时,因为最坏情况将要枚举15!种情况,因此只有采取dp。
本题有点类似于经典的数塔模型,此处用已完成的课程表示当前的状态,对于某门课程,0表示还未完成,1表示已完成,采用按位压缩的方式表示出所有的情况,因此最多有1<<15种状态。还有一点要注意,就是题目中所说的选择字典序最小的输出。具体的请看程序的具体实现。
//状态压缩dp,类似于数塔模型。 //对应位上,1表示已完成该课程,0表示未完成 //如001表示课程1已完成,而2,3未完成 #include<iostream> #include<string> using namespace std; const int INF=100000000; const int maxn=(1<<15); struct task { string name; int end,cost; }c[16]; struct { int now,days,score;//now为当前加入的课程编号,days为累加的天数,score为累加处罚分 }dp[maxn]; //输出路径 void path(int i) { if(i==0) return; path(i-(1<<dp[i].now)); cout<<c[dp[i].now].name<<endl; } int main() { int t,n,m; cin>>t; while(t--) { cin>>n; for(int i=0;i<n;i++) cin>>c[i].name>>c[i].end>>c[i].cost; //初始化 dp[0].now=0; dp[0].days=0; dp[0].score=0; m=(1<<n)-1; for(int i=1;i<=m;i++) dp[i].score=INF; for(int i=0;i<=m;i++)//类似于数塔,最底层表示一门作业也没完成(0),然后上一层表示已完成一门课程 { //依次递推,直到完成了所有的课程,即到达顶层(m) for(int j=0;j<n;j++)//课程 { int k=(1<<j); if((i&k)==0) {//若第j门课程还为完成 int cost=dp[i].days+c[j].cost-c[j].end; if(cost<0) cost=0; if(dp[i].score+cost<dp[i|k].score) { dp[i|k].score=dp[i].score+cost; dp[i|k].now=j; dp[i|k].days=dp[i].days+c[j].cost; } } } } printf("%d\n",dp[m].score); path(m); } //system("pause"); return 0; }