本文共 2546 字，大约阅读时间需要 8 分钟。

题目链接：

题目大意：

按照ACM/ICPC的比赛计分规则（解题数+20分钟罚时规则），给定比赛时间、总题数。

假设某个人是这样做题的： 

具体地说是这样的：

开始1小时(包括1小时整)内提交一次AC；

Ps：两个样例，把“//”加起来就是答案。

解题思路：

对于N道题规模的暴力搜索的时间复杂度是O(N⋅N!)。

然而题目的规模不大，N≤9，可取。

完全模拟真实比赛进程就可以了，由此可以得到两个基本的搜索出口：比赛时间到、题目全部解出（AK）。

每当到达搜索出口时，要将当前解与当前最优解比较并试图更新（最优解合并），这里需要O(N)的时间。

这个问题呢，仅以N为因子则时间复杂度不可能降低，最优算法即O(N⋅N!)，原因是你总是需要生成解题顺序的全排列来计算最优的方案。比如在比赛时长足够长（无限）的情况下，这也是一个有后效性的问题，不存在动态规划解。

AC 代码

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int maxn = 10;int H, N, T0;int fin_time, fin_used, fin_num;// 记录题目完成情况:1,完成 0,未完成  暂存题目标号  最终题目标号  题目完成时间  DEBUG时间int vis[maxn], tid[maxn], id[maxn], T[maxn], D[maxn];string name[maxn];void init(){    mem(vis, 0), mem(tid, 0), mem(id, 0);    fin_num = 0;    fin_time = INT_MAX;}void update(int num, int tme){    // 优先选择做出题数多的策略 or 做出题数一样，选择时间少的    if(num < fin_num || num == fin_num && tme >= fin_time) return;    // update    fin_num = num;    fin_time = tme;    for(int i = 0; i < num; i++)        id[i] = tid[i];}// 完成题数 用掉的时间 总消耗时间void dfs(int num, int used, int tme){    int fst_time = used + T[tid[num]];    int deg_times = (fst_time - 1) / 60;    int nxt_used = fst_time + deg_times * D[tid[num]];    int nxt_time = tme + nxt_used + deg_times * 20;    if(nxt_used <= H * 60) // 规定时间内能成功提交本题    {        num++;        if(num < N) // 还有未完成的题        {            for(int i = 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都不一样                }            }        }        else update(num, nxt_time); // 无题可做    }    else update(num, tme); // 超时。找到一种策略，回到上一层}int main(){    while( ~scanf("%d", &H) && H > 0 )    {        init();        scanf("%d%d", &N, &T0);        for( int i = 0; i < N; i++ )            cin >> name[i] >> T[i] >> D[i];        for( int i = 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(int i = 0; i < fin_num; i++)            printf("%s\n", name[id[i]].c_str());    }    return 0;}
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/84236320 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！