我是不是应该感谢这道题让我学会了对拍？ 对拍就是利用输入输出重定向弄到文件里面，具体代码就是这两行：
freopen("hwin.txt", "r", stdin); freopen("hwoutstd.txt", "w", stdout);字典序真的天坑……不过那个错误真的弱智到爆炸……
描述 小明是北京大学信息科学技术学院三年级本科生。他喜欢参加各式各样的校园社团。这个学期就要结束了，每个课程大作业的截止时间也快到了，可是小明还没有开始做。每一门课程都有一个课程大作业，每个课程大作业都有截止时间。如果提交时间超过截止时间X天，那么他将会被扣掉X分。对于每个大作业，小明要花费一天或者若干天来完成。他不能同时做多个大作业，只有他完成了当前的项目，才可以开始一个新的项目。小明希望你可以帮助他规划出一个最好的办法(完成大作业的顺序)来减少扣分。
输入 输入包含若干测试样例。 输入的第一行是一个正整数T，代表测试样例数目。 对于每组测试样例，第一行为正整数N（1 <= N <= 15）代表课程数目。 接下来N行，每行包含一个字符串S（不多于50个字符）代表课程名称和两个整数D（代表大作业截止时间）和C（完成该大作业需要的时间）。 注意所有的课程在输入中出现的顺序按照字典序排列。 输出 对于每组测试样例，请输出最小的扣分以及相应的课程完成的顺序。 如果最优方案有多个，请输出字典序靠前的方案。 样例输入 2 3 Computer 3 3 English 20 1 Math 3 2 3 Computer 3 3 English 6 3 Math 6 3 样例输出 2 Computer Math English 3 Computer English Math 提示 第二个测试样例, 课程完成顺序Computer->English->Math 和 Computer->Math->English 都会造成3分罚分, 但是我们选择前者,因为在字典序中靠前. 状压DP，旅行商问题变种。讲真如果不套旅行商模型真的想不到……一开始就想到了状态转移方程： dp[s]=dp[s-j]+c(j) 其中c(j)是做完s-j之后再做j的扣分数。 然后就不会了，一开始没想到状压不知道怎么循环（难不成15*15？差点做成枚举）最后还是看了讲义的思路。 AC代码如下：
#include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <string> using namespace std; struct info { string name; int ddl; int t; }; struct node { int pre; int thisone; int act; //all time consumed int minscore; node() { pre = 0; thisone = 100; act = 0; minscore = 0xffffff; } }; int main() { int T; cin >> T; while (T--) { node dp[(1 << 15) + 1]; info hw[15]; int num; cin >> num; for (int i = 0; i < num; ++i) { cin >> hw[i].name >> hw[i].ddl >> hw[i].t; //dp[(1 << i)].act = hw[i].t; //dp[(1 << i)].minscore = max(hw[i].t - hw[i].ddl, 0); //dp[(1 << i)].thisone = i; } dp[0].minscore = 0; int all = pow(2, num); for (int i = 1; i < all; ++i) { for (int j = 0; j < num; ++j) { if ((i >> j) & 1) { if (dp[i].minscore > dp[i & (~(1 << j))].minscore + max(dp[i & (~(1 << j))].act + hw[j].t - hw[j].ddl, 0)) { dp[i].pre = (i & (~(1 << j))); dp[i].minscore = dp[dp[i].pre].minscore + max(dp[dp[i].pre].act + hw[j].t - hw[j].ddl, 0); dp[i].act = dp[dp[i].pre].act + hw[j].t; dp[i].thisone = j; } else if (dp[i].minscore == dp[i & (~(1 << j))].minscore + max(dp[i & (~(1 << j))].act + hw[j].t - hw[j].ddl, 0)) { int kl = dp[i].pre, kr = (i & (~(1 << j))); vector <int> left; vector <int> right; left.push_back(dp[i].thisone); right.push_back(j); while (kl != 0) { left.push_back(dp[kl].thisone); right.push_back(dp[kr].thisone); kl = dp[kl].pre; kr = dp[kr].pre; } reverse(left.begin(), left.end()); reverse(right.begin(), right.end()); for (int k = 0; k < left.size(); ++k) { //一开始没加这个if if (right[k] > left[k]) { break; } if (right[k] < left[k]) { dp[i].pre = (i & (~(1 << j))); dp[i].minscore = dp[dp[i].pre].minscore + max(dp[dp[i].pre].act + hw[j].t - hw[j].ddl, 0); dp[i].act = dp[dp[i].pre].act + hw[j].t; dp[i].thisone = j; break; } } } } } } cout << dp[all - 1].minscore << endl; int k = all - 1; vector <int> output; while (k != 0) { output.push_back(dp[k].thisone); k = dp[k].pre; } for (int i = output.size() - 1; i >= 0; --i) { cout << hw[output[i]].name << endl; } } return 0; }还有就是，看到一篇链接中的代码在字典序排序方面极为巧妙，对拍用的就是那个标程： https://blog.csdn.net/yhjpku/article/details/80698249
