算法

DFS 考试临时抱佛脚

题目

来自洛谷的一道策略树题目：
https://www.luogu.com.cn/problem/P2392
这道题可以用 DFS 写也可以用背包 DP，这边选择 DFS。

题解

题目要求能够完成复习的最短时间，而且同时他、 kkksc03 可以同时计算 2 道不同但是同一科的题目，显然有左右脑之分。对于此， 可以将其分为两类，这两类所花费的时间要相近，最优的当然是两类时间一致。对于一类有放或不放两种选择，所以可以使用 dfs 进行求解。

同时，使用全局变量方便在递归中还能访问相关变量。

1
2
3
4

int nowTime, maxTime, ans = 0;
int maxDeep;
int sum;
int s[4], a[21];
  • s[4] 存储的是每门科目的习题数
  • a[21] 在之后会有覆盖的存储当前科目每道题目所消耗的时间
    其他变量之后再介绍。

dfs 函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void dfs(int x)
{
    if (x > maxDeep)
    {
        maxTime = max(maxTime, nowTime);
        return;
    }

    if (nowTime + a[x] <= sum / 2)
    {
        nowTime += a[x];
        dfs(x + 1);
        nowTime -= a[x];
    }
    dfs(x + 1);
}

这里再贴上 main 函数里面遍历 4 个科目并调用 dfs 函数的循环：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

for (int i = 0; i <= 4; i++ )
{
    nowTime = 0, maxTime = 0;
    maxDeep = s[i];
    sum = 0;
    for (int j = 1; j <= s[i]; j++)
    {
        cin >> a[j];
        sum += a[j];
    }

    dfs(1);
    ans += (sum - maxTime);
}

显然在每个科目开始，都会将 nowTime 、maxTime、sum 初始化为 0。

  • nowTime 作为递归过程当前所花费的时间，每一棵树递归到底部终止的时候，都会将 maxTime 与 nowTime 取最大值更新最大时间。
  • 上文有提到 maxTime，它就是用来存储当前的最优解，在遍历完成所有可能后，它就是最优解。
  • maxDeep 是最大深度，也就是题目的个数，作为递归终止回溯条件。
  • sum 是总的题目花费的时间，在一开始输入每道题花费的时间的时候就已经决定。

递归终止条件

1
2
3
4
5

    if (x > maxDeep)
    {
        maxTime = max(maxTime, nowTime);
        return;
    }

显而易见。

分支与剪枝

1
2
3
4
5
6
7

    if (nowTime + a[x] <= sum / 2)
    {
        nowTime += a[x];
        dfs(x + 1);
        nowTime -= a[x];
    }
    dfs(x + 1);

这个判断作为 dfs 分支剪枝是非常重要的，理解后其他都是 dfs 模板操作了。
上文有提到，整个 dfs 的核心就是分成两类，该两类要近乎相等就是最优解。你可能会想为什么我们要取最大值 maxTime 呢，实际上我们取的是在 [0, sum / 2] 这一块的最大值，也就是更接近中点的值。
我们只需要考虑一类，另一类就是我们需要的答案：最好的花费时间。
显然该 if 语句内和 if 外面的 dfs() 递归都很模板化，不过多讲述。

递归完成后

在每次递归后会得到该科目的最优解，我们只需要在答案中添加上该时间就好:

1

ans += (sum - maxTime);

后面循环后打印 ans 就是所需答案。

AC 代码

 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 <bits/stdc++.h>

using namespace std;

int nowTime, maxTime, sum;
int ans, maxDeep;
int s[4], a[21];

void dfs(int x)
{
    if (x > maxDeep)
    {
        maxTime = max(maxTime, nowTime);
        return;
    }

    if (nowTime + a[x] <= sum / 2)
    /*
     * 选取第 x 个元素后，累计值是否不超过总和的一半
     * 如果成立说明这个元素不会让累计值过半，允许选取
     * 如果不成立，选取会过半，跳过这个元素的选取，进入下面 dfs 尝试其他分支
     * ---
     * 这是一个分支限界的剪枝，避免搜索那些明显不满足条件的分支，提高搜索效率
     * 这个程序在寻找一个最优划分方案，使得某一部分的和尽可能接近总和的一半
     * ---
     * 只在保证第一组不过半的前提下才尝试添加题目到第一组
     * 这样 DFS 能找到的就是第一组达到的最大耗时，对应第二组耗时 `sum - maxTime` 就是该科目取得的最小完成时间
     */
    {
        nowTime += a[x];
        dfs(x + 1);
        nowTime -= a[x];
    }
    dfs(x + 1);
}

int main()
{
    cin >> s[0] >> s[1] >> s[2] >> s[3];

    for (int i = 0; i < 4; i++)
    {
        nowTime = 0;
        maxDeep = s[i];
        sum = 0;
        for (int j = 1; j <= maxDeep; j++)
        {
            cin >> a[j];
            sum += a[j];
        }
        maxTime = 0;
        dfs(1);
        ans += (sum - maxTime);
    }
    cout << ans;

    return 0;
}

参考资料

  1. 洛谷 深入浅出程序设计竞赛（基础篇） 高等教育出版社
  2. Claude Haiku 4.5 • 1x
萌ICP备20241614号