2.2.2 DFS之剪枝

深搜和宽搜都可以对应一颗搜索树，一般在叶子节点存的都是方案，提前判断不合法就是剪枝。

剪枝优化的常用策略

  1. 优化搜索顺序大部分情况下，我们应该优先搜索分支较少的结点(子节点比较少)，即选择策略较少的结点。可通过从大到小排序等手段。这样结合剪枝就能搜索更少的点如背包问题，先选大物体，再选小物体。

  2. 排除等效冗余不要搜索重复状态。如组合型问题，不考虑顺序。可以规定一个特定顺序。又如分组问题，规定新开一组时，直接将待放的第一个放入，因为组和组之间没有差别。分析时着重思考有没有两种搜索方案会是本质相同的，产生冗余。

  3. 可行性剪枝不合法(不满足题目条件)则提前退出

  4. 最优性剪枝已经差于当前最优解则退出

  5. 记忆化搜索(DP)

1. AcWing 165. 小猫爬山

搜索问题的思考顺序

先思考搜索顺序和决策操作，再尝试剪枝

本题和AcWing 1118. 分成互质组很相似，但本题由于对每组的总重量有限制，因而就不能采用贪心策略了——不具有最优子结构。需要额外进行总重量的判断。

因而本题只能够以枚举每只猫作为搜索顺序。从前往后枚举每只小猫应该放入哪个车上。

决策操作

  1. 依次尝试放入已开的车

  2. 放入一个新开的车注意这里新开一辆车是一种必备的方案，一定会被讨论。而AcWing 1118. 分成互质组中由于贪心策略，只有上一组全放满了，才会新开组。

本题和AcWing 1118. 分成互质组区别在于，本题使用的是动态数组的思路，为每个数字找组。分成互质组这题使用的是静态数组的思路，为每个组找数字

注意为了整体代码的一致性，刚开始以开0辆车为起点，依次尝试已开的车时即为0，然后再在dfs中开一辆新车。而不是直接以一辆车为起点。

分析时可以画搜索树辅助思考。

分析剪枝策略

  1. 优化搜索顺序从重量大的猫开始搜索；将所有猫按重量从大到小排序。重量大的占用更多空间，后续需要讨论的分支情况更少。

  2. 可行性剪枝如果当前车中的重量加上新猫的重量大于最大载重，就剪枝

  3. 最优性剪枝如果车的数量已经大于等于当前最优解就剪枝

C++

分组问题——动态数组的思路，为每个数字找组

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
59
60
61
62
63
// DFS之剪枝——AcWing 165. 小猫爬山
// 分组问题——动态数组的思路，为每个数字找组
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n, m;
int w[N];
int sum[N]; // 每辆车当前载重量，最多n辆车
int ans = N; // 注意初始赋值，求最小值，所以初始为最糟情况或无穷大

// u表示猫的下标，k表示将新开的车的下标，也是已开的车的数量
void dfs(int u, int k)
{
    // 最优性剪枝
    // 如果车的数量已经大于等于当前最优解就剪枝
    if (k >= ans) return;
    // 所有猫都放好了就返回
    if (u == n){
        ans = k;
        return;
    }

    for (int i = 0; i < k; i ++ )
        if (sum[i] + w[u] <= m){ // 可行性剪枝
        // 如果当前车中的重量加上新猫的重量大于最大载重，就剪枝(不执行搜索也可以认为是剪枝)
            sum[i] += w[u];
            dfs(u + 1, k);
            sum[i] -= w[u]; 
            // 恢复现场
        }

    // 新开一辆车
    // 注意每只猫都会将新开一辆车作为一种情况
    // 而不管前面的车是否放满（不能使用贪心策略）
    sum[k] = w[u];
    dfs(u + 1, k + 1);
    sum[k] = 0; // 恢复现场
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> w[i];

    // 剪枝优化——优化搜索顺序
    // 从重量大的猫开始搜索；将所有猫按重量排序
    sort(w, w + n , greater<int>());
    // sort(w, w + n);
    // reverse(w, w + n);

    dfs(0, 0);
    // 注意这里车数从0开始而不是1
    // 注意为了整体代码的一致性，刚开始以开0辆车为起点，依次尝试已开的车时即为0，然后再在dfs中开一辆新车。而不是直接以一辆车为起点。

    cout << ans << endl;

    return 0;
}

python

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
# DFS之剪枝——AcWing 165. 小猫爬山
# 分组问题——动态数组的思路，为每个数字找组
from sys import setrecursionlimit

def main():
    setrecursionlimit(5000)
    n, m = map(int, input().split())
    # 优化搜索顺序，先安排肥猫，后续的选择更少
    w = sorted([int(input()) for _ in range(n)], reverse=True)
    # sorted() 函数对所有可迭代的对象进行排序操作
    # w = w.sort(reverse=True) 
    s = [0] * n
    res = n
    
    # 回溯法，为每只猫猫找到合适的组
    # idx为当前的猫， s 为预设的空缆车，size 为当前开了几辆缆车
    def backtrace(idx, size):
        nonlocal res
        # 剪枝 and 刷新答案
        if size >= res or idx == n:
            res = min(res, size)
            return
        # 尝试将当前猫猫放入前 size 个缆车中
        for i in range(size):
            # 当前猫可以放到第 i 个缆车中
            if s[i] + w[idx] <= m:
                s[i] += w[idx]
                backtrace(idx + 1, size)
                s[i] -= w[idx]
        # 新开缆车，放入猫猫
        s[size] += w[idx]
        backtrace(idx + 1, size + 1)
        s[size] -= w[idx]
        
    backtrace(0, 0)
    print(res)
        
if __name__ == "__main__":
    main()

2. AcWing 166. 数独

数独问题的要求（限制）：

  • 每行都要有1~9

  • 每列都要有1~9

  • 每个九宫格都要有1~9

一. 搜索顺序

  1. 每次随机选取一个空格子进行填写，直到填满。或按照输入的前后顺序开始逐一填写。

  2. 每个格子填写时要枚举选哪个数

  3. dfs回溯搜索

决策方式

  1. 尝试填写所有能填的数

剪枝优化

  1. 优化搜索顺序选择备选方案最少的格子开始枚举，如果方案数相同则选择排在前面的格子

提前打表求出每个二进制数对应的1的个数，即备选方案数
2. 排除等效冗余本题可能会存在先填A为n再填B为m和先填B为m再填A为n的等效冗余。但当我们按1中特定顺序枚举时则不存在。
3. 可行性剪枝不能与行、列、九宫格有重复

细节部分处理——使用状态压缩+位运算优化

  1. 如何表示当某一行、列、九宫格前的填写状态由于不能重复的填写相当于组合问题，所以可用01向量表示状态故可采用九位二进制数表示当前行、列、九宫格已使用了哪些数。使用0表示不能再使用(已被用过)，1表示可以使用。之所以这样是为了后面方便使用lowbit()运算

  2. 如何判断是否与行、列、九宫格有重复可以对行、列、九宫格使用与运算&&来确定可选择的数字。

需注意，为了满足要求，每行、每列、每个九宫格的数字选取情况都用二进制表示了。但为了确定三个条件都满足的，就用&&取出同时为1的数。
3. 同时可以使用lowbit()运算依次取出所有1对应的要填的数。

位运算

  1. 求n的二进制表示中第k位是几：n >> k && 1
    先把第k位移到个位(n >> k)，然后取出( n >> k && 1)

  2. lowbit(x)操作，返回x最右端一位的1所代表的大小x & -x
    负数的补码是原码取反加1x & -x == x & (~x + 1)。已知其补码相对于原码，最右端的1和其右面的0是不变的，其余全部取反，因而x & -x后只剩下最右端的1了，其余全变成0。这是树状数组的一个基本操作。用途之一是用来求一个数x二进制表示中1的个数

打表预处理优化->两个数组

  • 求出所有二进制数中有多少1，用于优化搜索顺序——分枝少的格子先填写

  • lowbit返回时最右端的1所代表的大小，第k位的代表$2^k$，需要快速求出k，因此建立一个对应的映射函数直接查询

C++

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// DFS之剪枝——AcWing 166. 数独
// 剪枝优化+位运算+打表
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 9, M = 1 << N;

int ones[M], map[M];
// ones用于求出每个二进制数有多少个1，用于优化搜索顺序——选取备选方案最少的格子先填写
// map用于存储2^k取对数为多少(即k)，因为lowbit求出的是2^k，而我们想要的是k
int row[N], col[N], cell[3][3]; // 存储行、列、九宫格的状态
char str[100]; // 使用字符串存储整个表

// 预处理表示行、列、九宫格状态的数组，都初始化为0~8位全1，即为(1 << N) - 1
void init(){
    for (int i = 0; i < N; i ++ )
        row[i] = col[i] = (1 << N) - 1;
        // (1 << N) - 1括号不可少，一定不要忘了位运算的运算级较低

    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            cell[i][j] = (1 << N) - 1;
}

// 更新整个图、每行、每列、每个九宫格的当前填写状况，包括填写和恢复两方面
// 在(x,y)位置填写数字t，is_set表示两种选择——填写或恢复原状（删掉已填写的数）
void draw(int x, int y, int t, bool is_set){
    // 注意变成字母
    if (is_set) str[x * N + y] = '1' + t;
    // 注意这里必须这样写，因为maps中返回的t表示的位数，而在二进制中第0位表示的是1，第i位表示的是i+1，所以要填写的数字时t + '1'
    // 删除
    else str[x * N + y] = '.';
    
	// t的二进制位数所对应的值的大小(2^t)
    int v = 1 << t;
    // 如果删除操作就减去v，填写操作就加上v
    if (!is_set) v = -v;
    
    // 注意填写后就不能再用了，为0，所以是减去
    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v; 
}

// 使用lowbit位运算获取最右端一位的1所代表的大小
int lowbit(int x){
    return x & -x;
}

// 利用与运算求(x, y)位置能填哪些数，获取填写情况对应的二进制数
int get(int x, int y){
    return row[x] & col[y] & cell[x / 3][y / 3];
    // 使用与运算找到行、列、九宫格来取可选择的数字
}

bool dfs(int cnt){
    if (!cnt) return true;

    int minv = 10; // 存储分支最小的空格的分支数，初值大于最遭情况
    int x, y;
    // 求分支最小的空格
    for (int i = 0; i < N; ++ i)
        for (int j = 0; j < N; ++ j)
            if (str[i * N + j] == '.'){
                // 获取填写情况对应的二进制数
                int state = get(i, j); 
                if (ones[state] < minv){
                    minv = ones[state];
                    x = i, y = j;
                }
            }

    int state = get(x, y);
    // 枚举取出所有1，尝试所有能填的数
    for (int i = state; i; i -= lowbit(i)){
        int t = map[lowbit(i)]; // 转换为对应的填写数字（取对数），注意查找使用的是lowbit(i)
        draw(x, y, t, true); // 更新填写
        if (dfs(cnt - 1)) return true; // 本题只有唯一解， 为真直接返回，否则回溯时会删除获得的结果
        draw(x, y, t, false); // 恢复原状
    }
    return false;
}

int main(){
    // 打表
    for (int i = 0; i < N; ++ i) map[1 << i] = i;
    // 1 << i为2^i的值
    // map用于存储2^k取对数为多少(即k)，因为lowbit求出的是2^k，而我们想要的是k

    // 打表法，预处理出每个数的二进制中有多少个1
    // 由于一共9个数，所以用0~8位表示即可，故枚举到(1 << 9) - 1，即M
    for (int i = 0; i < M; ++ i)
        for (int j = 0; j < N; ++ j)
            // 位运算
            // 求n的二进制表示中第k位是0还是1，n >> k && 1
            ones[i] += i >> j & 1;
    	    
    while (cin >> str, str[0] != 'e'){
        // 预处理表示行、列、九宫格状态的数组，初始化为全1
        init();
        
        // cnt表示还有多少个空位
        int cnt = 0;
        
        // 填入输入的状态
        for (int i = 0, k = 0; i < N; ++ i)
            for (int j = 0; j < N; ++ j, ++ k)
                if (str[k] != '.'){
                    // 数字的大小
                    // 这里写成-'1'而不是-'0'是为了便于后面求二进制时使用
                    // 因为二进制时t表示位数，而填写的数字为t + '1'，所以这里统一格式
                    int t = str[k] - '1';
                    // 填入对应状态
                    draw(i, j, t, true);
                    
                }
                else ++ cnt;

        dfs(cnt);
        // 形参为还剩多少空格待填

        puts(str);
    }
    return 0;
}

python

TLE超时

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# DFS之剪枝——AcWing 166. 数独
# 剪枝优化+位运算+打表
# python会超时
def main():
    N = 9
    M = 1 << N
    ones = [0] * M
    maps = {}
    
    for i in range(M):
        for j in range(N):
            ones[i] += i >> j & 1
     
    for i in range(N):
        maps[1 << i] = i 
        
    def draw(x, y, t, is_set):
        if is_set:
            s[x * N + y] = str(t)
        else:
            s[x * N + y] = '.'
        
        v = 1 << (t - 1)
        if not is_set:
            v = -v
        row[x] -= v
        col[y] -= v
        cell[x // 3][y // 3] -= v
        # row[x] ^= v
        # col[y] ^= v
        # cell[x//3][y//3] ^= v
    
    def lowbit(x):
        return x & -x
    
    def get(x, y):
        return row[x] & col[y] & cell[x // 3][y // 3]
    
    def backtrace(cnt):
        if not cnt:
            return True
        
        minv = 10
        x, y = 0, 0 
        for i in range(N):
            for j in range(N):
                if s[i * N + j] == '.':
                    state = get(i, j)
                    if ones[state] < minv:
                        minv = ones[state]
                        x, y = i, j
        state = get(x, y)
        while state:
            t = maps[lowbit(state)] + 1
            # 这里的加1一定不要少
            # 因为maps中返回的t表示的位数，而在二进制中第0位表示的是1，第i位表示的是i+1，
            # 所以要填写的数字时t + 1
            draw(x, y, t, True)
            if backtrace(cnt - 1):
                return True
            draw(x, y, t, False)
            state -= lowbit(state)
        return False
    
    while True:
        g = input()
        if g == "end":
            return
        s = list(g)
        # python中字符串是一个不可变类型，不能直接改变字符串中某个字符的值，
        # 需要另建一个存字符的列表处理字符

        col = [(1 << N) - 1] * N;
        row = [(1 << N) - 1] * N
        cell = [[(1 << N ) - 1] * 3 for _ in range(3)]

        # cnt统计棋盘中空位个数
        cnt = 0
        for i in range(N):
            for j in range(N):
                if s[i * N + j] != '.': 
                    t = int(s[i * N + j])
                    draw(i, j, t, True)
                else:
                    cnt += 1
        backtrace(cnt)
        print("".join(s))
        # 将列表中字符重新合并成字符串

if __name__ == "__main__":
    main()

3. AcWing 167. 木棒

问题转化：

本题相当于将若干个数分成多组，使每组总和相等，求解最多能分成多少组

这里一个值得注意的点是，将“每组总和最小为多少”转化为”最多能分成多少组“

搜索顺序：

  1. 枚举木棒长度：从最小长度开始，枚举所有可能构成的木棒长度，第一个可行解即最优解

  2. 枚举选择小木棍拼接木棒：对于固定长度，依次枚举每根木棒有哪些小木棍构成（相当于一个组一个组的划分好）。小木棍的遍历寻找为组合型枚举

    组内小木棍和木棒的顺序都可取任意特定顺序

剪枝优化：

  1. 可行性剪枝：

    • 组成的木棒长度要是总长度的约数
    • 放入的小木棍长度加上木棒当前长度要小于固定长度

  2. 优化搜索顺序：为了更少的备选方案，对小木棍按长度从大到小枚举枚举

  3. 排除等效冗余：

    这里的冗余要考虑两个方面，首先是每个木棒内部的小木棍不存在顺序；其次木棍间也不存在顺序。前者使用组合数方式枚举即可，后者相对更复杂，因为其还涉及到方案的可行性问题。一般而言，一个小木棍无法用于当前木棒的构成并不能说明方案不可行，还需要继续枚举其他小木棍。但可以考虑一些特殊的情况，用当前小木棍的失败直接排除剩余的一部分小木棍乃至所有小木棍，减少枚举的小木棍数和木棒数。

    • 按照组合数方式枚举：规定特定顺序，每次从上次枚举的下一个开始处理——设置形参start

    • 如果当前小木棍加到当前木棒中不可行，则直接略过后面所有长度相等的小木棍（小木棍间的冗余）

    • 如果当前木棒放第一根小木棍u导致这根木棒凑不成length，则不用继续枚举，整个方案一定失败（前提逻辑是我们放入第一根小木棍后会尝试搜寻所有以其为第一部分的所有可能的方案。虽然到了最后我们把第一根小木棍u替换掉了可能会构成当前木棒，但后面其同样还会导致构不成木棒，继续枚举是木棒间的冗余）

    • 如果当前木棒的最后一根小木棍u放在这里能构成了当前木棒，但搜寻后续方案失败了，则这不是因为这根小木棍导致的，且整个方案一定失败。换掉当前小木棍用于后续木棒也一样无法构成，不要再去尝试构建当前木棒的其他方案。（换句话说，已用于构成木棒的小木棍的在木棒间的使用顺序变化不会影响方案的可行性，不用做无意义的替换尝试，构成了的就不要变动了。同时如果当前小木棍构成了当前木棒，但递归搜索后续方案时失败了，就一定失败了，不要再去重新尝试构建当前木棒的其他方案，该层递归直接返回false）

    注意放在中间的小木棍是不一样的，其所在木棒无法构成可能是该小木棍和前面组成该木棒的某个小木棍不合适，可以重新组合，不一定就无法构成。

C++

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// DFS之剪枝——AcWing 167. 木棒
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 70;

int n;
int w[N];
int sum, length;
bool st[N];

// u表示当前构建木棒序号（从0开始，已完全构成木棒数量=u），s表示当前木棒已构建的长度， start用于组合类枚举记录枚举位置
// 当u=sum/length时，实际已经构建好了所有木棒，直接返回
bool dfs(int u, int s, int start){
    if (u * length == sum) return true;
    // 如果当前木棒已被构建好，则直接返回对下一根木棒的构建
    // 注意这里start也要置为0
    if (s == length) return dfs(u + 1, 0, 0);
	
    // 剪枝优化——排除等效冗余，按照组合数方式枚举
    for (int i = start; i < n; i ++ ){
        // 可行性剪枝——放入的小木棍长度加上木棒当前长度要小于固定长度
        if (st[i] || s + w[i] > length) continue;
        st[i] = true;
        // 判断当前方案是否合法，进行递归
        if (dfs(u, s + w[i], i + 1)) return true;
        st[i] = false; // 回溯
        
	    // 当前小木棍失败后的剪枝优化
        // 剪枝优化——排除等效冗余，第一根小木棍不可行则一定不可行
        if (!s) return false;
        // 剪枝优化——排除等效冗余，第一根小木棍不可行则一定不可行
        if (s + w[i] == length) return false;
        // 剪枝优化——排除等效冗余，略过后面长度相等的小木棍
        // 能这样写也是因为先进行了排序
        int j = i;
        while (j < n && w[j] == w[i]) j ++ ;
        // 注意因为for循环也会执行i++，所以这里随后要写i=j-1
        i = j - 1;  
    }
    return false;
}

int main(){
    while (cin >> n, n){
        // 初始化
        memset(st, 0, sizeof st);
        sum = 0;

        for (int i = 0; i < n; i ++ ){
            cin >> w[i];
            sum += w[i]; // 总长度
        }
	    // 剪枝——优化搜索顺序，长度从大到小枚举小木棍
        sort(w, w + n);
        reverse(w, w + n);
        // sort(w, w + n, greater<int>())
	    
        // 枚举木棒长度
        length = w[0];
        // 不会死循环——最遭情况是所有小木棍共同构成一根木棒
        while (true){
            // 可行性剪枝
            if (sum % length == 0 && dfs(0, 0, 0)){
                cout << length << endl;
                break;
            }
            length ++ ;
        }
    }
    return 0;
}

python

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
# DFS之剪枝——AcWing 167. 木棒
def main():
    # cnt 表示当前在组合第几根棍子，从0开始，已完全构成木棒数量=cnt
    # cur 表示当前棍子的长度
    # st  表示当前从第几根小棍子开始枚举
    def backtrace(cnt, cur, start):
        if cnt * length == tot:
            return True
        # 如果当前木棒已被构建好，则直接返回对下一根木棒的构建
        if cur == length:
            return backtrace(cnt + 1, 0, 0)
        
        fail = -1
        for i in range(start, n):
            # 可行性剪枝，不能是用过的、组合后长度超过length的
            # 剪枝优化——排除等效冗余，失败后略过后面长度相等的小木棍
            if vis[i] or w[i] == fail or cur + w[i] > length:
                continue
            vis[i] = True
            if backtrace(cnt, cur + w[i], i + 1):
                return True
            vis[i] = False
            # 到这里说明当前方案失败，记录失败的棍子长度
            fail = w[i]
            # 注意这里和C++写法的不同-->无法通过直接修改i的值跳过循环，所以采用标记法
            
            # 剪枝优化——排除等效冗余
            # 失败了，且当前小棍子是第一根或者最后一根，说明后续也找不到合法方案来安放它
            if not cur:
                return False
            if cur + w[i] == length:
                return False

        return False
    
    while True:
        n = int(input(), )
        if not n:
            return
        # 优化搜索顺序，大的先搜
        w = sorted(list(map(int, input().split())), reverse=True)
        # length恰从最长小木棒开始搜
        tot, length = sum(w), w[0]
        vis = [False] * n
        while length <= tot:
            # 可行性剪枝
            # 枚举 [m, tot] 之间能被 tot 整除的单根原棍长度
            if not tot % length and backtrace(0, 0, 0):
                print(length)
                break
            length += 1
        
if __name__ == "__main__":
    main()

4. AcWing 168. 生日蛋糕

整体思路

问题为给定总体积$N\pi$和总层数$M$，且从上到下内层半径$R$和高$H$严格单调递增，求扣除底面的最小表面积

题目限制条件较复杂，由$1\leq M\leq20$推断可以使用暴搜

记最底层为 m, 很容易观察得出，表面积的公式为
$$
\begin{align}
S_{总} & = S_{侧面} + S_{上表面} \\
& = S_{所有层侧面积之和} + S_{第m层上表面积} \\
& = \sum_{i=1}^{m}2\pi R_iH_i +\pi R_m^2 \\
\end{align}
$$
而体积为
$$
V_总 = \sum_{i=1}^{m}\pi R_i^2H_i
$$

由题意，$\pi$可以被忽略掉。

此外可以发现，利用单调递增的性质，每层高度和半径的最小值恰是该层的编号u（从最高层开始且初始编号为1）。

有了两个公式，还有题目给出的每层最小高度和最小半径，就知道可以用剪枝 + 暴搜来做这个题

20210127003014554

搜索顺序

一层一层搜索半径和高

剪枝优化

image-20230226111159177

1. 优化搜索顺序

  1. 层间：从下到上搜索，先搜体积和表面积大的，减少分支（由于蛋糕从下往上半径、高度依次递减，故体积也随之递减，由于总体积是确定不变的，所以我们从下往上枚举，最底层的蛋糕对应的分支数量最少。）

  2. 层内：先枚举半径再枚举高（半径相对于高来说对体积和表面积的影响较大，半径$R$在公式中是平方级别$R^2$，而高是线性级别$H$），且两者都从大到小枚举

为此，在枚举每一层蛋糕时，需要记录当前层数$u$，当前蛋糕体积$v$和表面积$s$

2. 可行性剪枝

结合单调性放缩，利用高度$h$和半径$r$的范围及体积的约束进行剪枝

记总体积为$N$，当前层编号为$u$，高度为 $H_u$，半径为 $R_u$， 体积为 $V_u$，第 $m$ 层到第$u+1$层体积的累计值为 $V$

  1. 对于$R_u$，当前为第$u$层， 第$u$层的体积为 $V_u$。$R_u$的下界应该是当前的层号$u$，R 的上界应该由两部分决定

    • $u+1$层半径$R_{u+1}$的约束：由于半径随层数单调递增，所以 $R_u \leq R_{u+1}-1$
    • 第$u$层体积 $V_u$的约束：由于第$u$层体积一定小于$N-min\sum_{i=1}^{u-1}V_i-V$，即 $V_u = R_u^2H_u \leq N-min\sum_{i=1}^{u-1}V_i-V$，又由于$H_u$同样有下界$u$，所以$R_u \leq \sqrt{\frac{n-min\sum_{i=1}^{u-1}V_i - V}{u}}$

取这两者的最小值, 故有以下等式成立

$$
u \leq R_u \leq min \lbrace R_{u+1}-1, \sqrt{\frac{n-min\sum_{i=1}^{u-1}V_i - V}{u}} \rbrace
$$

  1. 对于第$u$层高度$H_u$的推导同理，$H_u$的下界为层号$u$，$H_u$的上界由也两部分决定

    • $u+1$层高度$H_{u+1}$的约束：$H_u \leq H_{u+1}-1$
    • 第$u$层体积 $V_u$的约束：由于第$u$层体积一定小于$N - min \sum_{i=1}^{u-1} V_i - V$，即 $V_u = R_u^2 H_u \leq N - min \sum_{i=1}^{u-1} V_i - V$，又由于$R_u$此时已被枚举确定，所以$H_u \leq \frac{n - min \sum_{i=1}^{u-1} V_i - V}{R^2_u}$

故同理可得出下列等式
$$
u \leq H_u \leq \min \lbrace H_{u+1} - 1, \frac{n-min\sum_{i=1}^{u-1}V_i - V}{R_u^2} \rbrace
$$

  1. 体积的可行性剪枝：

    记第 1 到第 $u$ 层体积的累计值为$V_{1-u}$，利用不等式$V + V_{1-u} = N$进行剪枝

    首先需预处理前 $u$ 层体积$V_{1-u}$的最小值 $min\sum_{i=1}^{u}V_i$，此时有$R_i=H_i=u(i=1,\cdots,u)$，则
    $$
    V + min\sum_{i=1}^{u}V_i \leq n
    $$

3. 最优性剪枝

放缩挖掘不等式关系，研究表面积的最优性剪枝

记第 $m$ 层到第 $u+1$ 层表面积的累计值为 $S$, 第 1 到第 $u$ 层表面积的累计值为$S_{1-u}$

利用不等式$S + S_{1-u} < ans$则有以下两种剪枝

  1. 预处理出$S_{1-u}$的最小值为 $min\sum_{i=1}^{u-1}S_i$，此时有$R_i=H_i=u(i=1,\cdots,u)$，则
    $$
    S + \min\sum_{i=1}^{u} S_i < ans
    $$

  2. 利用放缩法推表面积公式和体积公式的关系，进一步剪枝

    • 第一层到第$u$层的表面积有（不考虑 $\pi$）

$$
S_{1-u} = 2 \sum_{i=1}^{u} R_i H_i = \frac{2}{ R_{u+1} } \sum_{i=1}^{u} R_{u+1} R_i H_i > \frac{2}{ R_{u+1} } \sum_{i=1}^{u} R_i^2 H_i
$$

  • 第一层到第 u 层的体积有

$$
n - V = \sum_{i=1}^{u} R_i^2 H_i
$$

所以惊奇地发现
$$
S_{1-u} >\frac{2(n-V)}{R_{u+1}}
$$
因此 $S_总 = S + S_{1-u}>=S_{ans}$，即

$$
S + \frac{2(n-V)}{R_{u+1}} \geq S_{ans}, \ \ \ u=0时取等
$$

时就可以剪枝掉（最优性剪枝)

C++

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
59
60
61
62
63
64
65
66
// DFS之剪枝——AcWing 168. 生日蛋糕
// 数学推导放缩剪枝
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 23, INF = 1e9;

int n, m;
// R，H存每一层半径和高度
int R[N], H[N];
// 前u层总体积，总侧面积的最小值，相当于前缀和
int minv[N], mins[N];
int ans = INF; // 表面积答案

// u表示当前这一层编号，v表示从m到u+1层的总体积（不含本层），s表示从m到u+1层的总共的面积（不含本层）
void dfs(int u, int v, int s){
    // 可行性剪枝——体积约束，已构建层的总体积+待构件层的最小总体积<=总体积
    if (v + minv[u] > n) return;
    // 最优性剪枝——最优表面积，已构建层的表面积+待构件层的最小表面积<当前最优表面积
    if (s + mins[u] >= ans) return;
    // 最优性剪枝——放缩不等式，已构建层的表面积+待构件层的最小表面积<当前最优表面积
    if (s + 2*(n-v)/R[u+1] >= ans) return;
    
    // u = 0时表明已经枚举完毕，判断当前体积是否等于n，若是，更新表面积
    if (!u){
        if (n == v) ans = s;
        // 注意当前总体积不等于n是不要更新面积，但也要return
        return;
    }
    
    // 剪枝之优化搜索顺序——先从大到小枚举半径，再从大到小枚举高度
    // 可行性剪枝——只在已确定的可行范围内枚举，范围由单调性放缩得到
    for (int r = min(R[u + 1] - 1, (int)sqrt((n - minv[u - 1] - v)/u)); r >= u; -- r)
        for (int h = min(H[u + 1] - 1, (int)(n - minv[u - 1] - v)/ (r * r)); h >= u; -- h){
            int t = (u == m) ? r * r : 0; // 若是最底层，则要把顶部面积加上
            R[u] = r, H[u] = h;
            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
            // 这里需注意，回溯时，R[u], H[u]可直接被覆盖，而并没有改变其他的属性，所以无需恢复现场
        }
    
}

int main(){
    scanf("%d%d", &n, &m);
    
    // 预处理求出前u层总体积，总侧面积的最小值
    for (int i = 0; i < m; ++ i){
        // 最小时，R和H都等于对应层的编号
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
        // 这里是一个小trick，minv[]和mins[]是按蛋糕从上到下计算的每一层的极限体积和侧面积
        // 但是最后搜索是从下到上搜索，这样min[]前缀和存的就是还未使用的体积和表面积了
    }
    
    // 哨兵，由于第m层R和H小于等于第m+1层R和H的值减1，所以这里将m+1层初始化为INF避免影响
    R[m + 1] = H[m + 1] = INF;
    dfs(m, 0, 0);
    if (ans == INF) 
        ans = 0;
    printf("%d\n", ans);
    return 0;
}

python

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
# DFS之剪枝——AcWing 168. 生日蛋糕
# 数学推导放缩剪枝
from math import inf
def main():
    MAX_M = 24
    n = int(input())
    m = int(input())
    # 记录前 u 层的最小体积和侧面积
    minv, mins = [0] * MAX_M, [0] * MAX_M
    # 记录搜索时每一层的半径和高度
    R, H = [0] * MAX_M, [0] * MAX_M
    res = inf
    
    # 预处理边界以及剪枝用的数据
    R[m + 1] = H[m + 1] = inf
    # 注意u从1到m
    for i in range(1, m + 1):
        minv[i] = minv[i - 1] + i ** 3
        mins[i] = mins[i - 1] + 2 * i ** 2
    
    # 爆搜，剪了很多枝的爆搜
    # n 是体积，m 是层数
    def backtrace(u, v, s):
        nonlocal res
        if v + minv[u] > n: 
            return
        # 推出的公式剪枝，筛掉一定不是答案的分支
        if s + max(mins[u], 2 * (n - v) // R[u + 1]) >= res:
            return
        
        if not u:
            # 蛋糕做好了且是当前最优解
            if v == n:
                res = s
            return 
        
        sr = min(R[u + 1] - 1, int(((n - minv[u - 1] - v) / u)**0.5))
        # 优化搜索顺序，从最大的半径开始枚举
        for r in range(sr, u - 1, -1):
            # 当前是最底层时，不要忘了加上顶部的表面积
            t = r * r if u == m else 0
            sh = min(H[u + 1] - 1, int((n - minv[u - 1] - v) / (r * r)))
            # 优化搜索顺序，从最大的高度开始枚举
            for h in range(sh, u - 1, -1):
                R[u], H[u] = r, h
                # 递归上一层
                backtrace(u - 1, v + r * r * h, s + 2 * r * h + t)
    # 从最底层开始向上枚举
    backtrace(m, 0, 0)
    # 无解输出 0
    print(0 if res == inf else res)
    
if __name__ == "__main__":
    main()