题目链接：点击打开链接
题目大意：按照ACM/ICPC的比赛计分规则（解题数+20分钟罚时规则），给定比赛时间、总题数。
假设某个人是这样做题的：
1. 用一定时间通读所有的题，计算出解出每个题目所需的时间，以及如果错了，调试一次所需的时间。
2. 他一旦开始做某题，不做出来就不换题（一不做二不休）。
3. 对于每道题，他第一次提交的时间决定了他需要调试的次数。
具体地说是这样的：
开始1小时(包括1小时整)内提交一次AC；
第二个小时内提交需要调试一次才能AC；
……
第N个小时内提交需要提交N次才能AC；
问题是要帮他确定一个可以获得尽量高排名的做题顺序：在解题量尽量高的前提下让罚时尽量小。
Ps：两个样例，把“//”加起来就是答案。
解题思路：
对于N道题规模的暴力搜索的时间复杂度是O(N⋅N!)。
然而题目的规模不大，N≤9，可取。
完全模拟真实比赛进程就可以了，由此可以得到两个基本的搜索出口：比赛时间到、题目全部解出（AK）。
每当到达搜索出口时，要将当前解与当前最优解比较并试图更新（最优解合并），这里需要O(N)的时间。
这个问题呢，仅以N为因子则时间复杂度不可能降低，最优算法即O(N⋅N!)，原因是你总是需要生成解题顺序的全排列来计算最优的方案。比如在比赛时长足够长（无限）的情况下，这也是一个有后效性的问题，不存在动态规划解。
AC 代码
usingnamespacestd; typedeflonglongll; constintmaxn=10; intH, N, T0; intfin_time, fin_used, fin_num; // 记录题目完成情况:1,完成 0,未完成 暂存题目标号 最终题目标号 题目完成时间 DEBUG时间intvis[maxn], tid[maxn], id[maxn], T[maxn], D[maxn]; stringname[maxn]; voidinit() { mem(vis, 0), mem(tid, 0), mem(id, 0); fin_num=0; fin_time=INT_MAX; } voidupdate(intnum, inttme) { // 优先选择做出题数多的策略 or 做出题数一样，选择时间少的if(num<fin_num||num==fin_num&&tme>=fin_time) return; // updatefin_num=num; fin_time=tme; for(inti=0; i<num; i++) id[i] =tid[i]; } // 完成题数 用掉的时间 总消耗时间voiddfs(intnum, intused, inttme) { intfst_time=used+T[tid[num]]; intdeg_times= (fst_time-1) /60; intnxt_used=fst_time+deg_times*D[tid[num]]; intnxt_time=tme+nxt_used+deg_times*20; if(nxt_used<=H*60) // 规定时间内能成功提交本题 { num++; if(num<N) // 还有未完成的题 { for(inti=0; i<N; i++) // 尝试每个可走的岔路 { if(!vis[i]) { vis[i]=1; tid[num]=i; dfs(num, nxt_used, nxt_time); vis[i]=0; // 不用num--，num是形参，每层的num都不一样 } } } elseupdate(num, nxt_time); // 无题可做 } elseupdate(num, tme); // 超时。找到一种策略，回到上一层} intmain() { while( ~scanf("%d", &H) &&H>0 ) { init(); scanf("%d%d", &N, &T0); for( inti=0; i<N; i++ ) cin>>name[i] >>T[i] >>D[i]; for( inti=0; i<N; i++ ) { vis[i] =1; tid[0] =i; dfs(0, T0, 0); vis[i] =0; } printf("Total Time = %d\n", fin_time); for(inti=0; i<fin_num; i++) printf("%s\n", name[id[i]].c_str()); } return0; }
