最开始以为是贪心，不过写到一半发现不对，看了一下讨论，知道需要使用状态压缩DP，现在还没有使用深搜实现（据说可以）晚上实现一下，道理应该是类似的。前面做八数码，至今未果，就说需要状态压缩。这个太神奇了，因为题目的数据量为15，所以采用移位压缩。即100代表第三个（注意index）的转台为完成。RE了很多次，才发现异或后求得的不是index。。。而且原来的输入数据本身就是字典序，不需要再strcmp，就一直RE在那个if了。
#include <stdio.h>
#include <stdlib.h>
#include <string.h> #define MAXNUM 16
#define MAXDP 1<<15 typedef struct {
int pre;
int reduce;
int complete;
} dp_st; dp_st dps[MAXDP];
char visit[MAXDP];
char stack[MAXNUM][]; typedef struct {
char name[];
int dead, need;
} homework_st; homework_st homeworks[MAXNUM]; void printCourse(int end) {
int top=, now=end, id, tmp; while (now) {
id = now ^ dps[now].pre;
tmp = ;
while (id) {
id = id>>;
++tmp;
}
strcpy(stack[top++], homeworks[tmp-].name);
now = dps[now].pre;
} while (top) {
--top;
printf("%s\n", stack[top]);
}
} int main() {
int case_n, n, len;
int i, j, k, code, tmp, complete, reduce;
//FILE *fout = fopen("data", "w"); scanf("%d", &case_n); while (case_n--) {
scanf("%d%*c", &n);
for (i=; i<n; ++i)
scanf("%s %d %d", homeworks[i].name, &homeworks[i].dead, &homeworks[i].need);
memset(visit, , sizeof(visit));
len = <<n;
dps[].pre = -;
dps[].reduce = ;
dps[].complete = ;
visit[] = ;
// 0~len-1
for (i=; i<len-; ++i) {
for (j=; j<n; ++j) {
code = <<j;
// code is not done
if ((i&code) == ) {
k = i|code;
complete = dps[i].complete + homeworks[j].need;
tmp = complete - homeworks[j].dead;
if (tmp < )
tmp = ;
reduce = dps[i].reduce + tmp;
if ( visit[k] ) {
if (reduce < dps[k].reduce) {
dps[k].reduce = reduce;
dps[k].complete = complete;
dps[k].pre = i;
}
/* No need and tmp need to while(){>>1} again
else if (reduce == dps[k].reduce){
tmp = dps[k].pre ^ k;
if (strcmp(homeworks[j].name, homeworks[tmp].name) < 0) {
dps[k].reduce = reduce;
dps[k].complete = complete;
dps[k].pre = i;
}
}*/
} else {
visit[k] = ;
dps[k].reduce = reduce;
dps[k].complete = complete;
dps[k].pre = i;
}
}
}
}
/*
for (i=0; i<len; ++i)
fprintf(fout, "%d: pre=%d,reduce=%d,complete=%d\n", i,dps[i].pre,dps[i].reduce,dps[i].complete);
*/
printf("%d\n", dps[len-].reduce);
printCourse(len-);
} //fclose(fout);
return ;
}