题目大意
你要完成n份作业（n最大15）每份作业有需要完成的时间和时限，不能在要求的时间内完成每晚一个时间单位扣一分，问扣分最少是多少 在扣分最少的情况下 要求输出完成顺序 要输出所有可能种字典序排的一份
题解
乍一看之下，简单 简单~ 不就是按时限排个序就知道最小值了吗 唉等等 要求输出字典序最小的情况，这就有些意思了 因为这时候时限小的可能由于字典序问题不一定排在前面 举例来说
math 20 1
se 5 1
这种情况下时限并没有任何意义 不能简单排序了之
那要怎么办呢？考虑到n给的很小，我一下子之前做过想到了状压dp 对于每个状态，搜索置为1的看看能不能从那个状态过来，这样遍历即可 由于输入自然的保证了顺序 我们只需要搜索时倒着搜索就可以保证字典序了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<stack>
using namespace std;
struct subject{
string classname;
int endtime,lasttime;
};
subject classes[20];
struct node{
int nowtime,score,lastindex;
}dp[1<<17];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
char tmp[120];
for(int i=0;i<n;++i){
scanf("%s%d%d",tmp,&classes[i].endtime,&classes[i].lasttime);
classes[i].classname=tmp;
}
memset(dp,0,sizeof(dp));
int s=1<<n;
for(int i=1;i<s;++i){
dp[i].score=0x3fffffff;
for(int j=n-1;j>=0;--j){
int t=1<<j;
if(i&t){
int addscore=dp[i&(~t)].nowtime+classes[j].lasttime-classes[j].endtime;
if(addscore<0){
addscore=0;
}
if(dp[i&(~t)].score+addscore<dp[i].score){
dp[i].score=dp[i&(~t)].score+addscore;
dp[i].nowtime=dp[i&(~t)].nowtime+classes[j].lasttime;
dp[i].lastindex=j;
}
}
}
}
stack<string> order;
int t=(1<<n)-1;
printf("%d\n",dp[t].score);
while(t){
order.push(classes[dp[t].lastindex].classname);
t&=(~(1<<dp[t].lastindex));
}
while(!order.empty()){
printf("%s\n",order.top().c_str());
order.pop();
}
}
return 0;
}
|