击杀黄金蛋糕人马（dfs + 记忆化搜索）（难）

题解：

这段代码实现了一个递归的记忆化搜索算法，用于解决一个求最大蛋糕面积下限的问题。下面解释一下其递归思路：

1. 定义状态

设 ways[w][h][m] 表示当前蛋糕的宽度为 w，高度为 h，已经切了 m 刀时，最大蛋糕面积的下限。

2. 状态转移

对于当前的蛋糕，可以选择竖着切一刀或者横着切一刀。竖着切一刀会将蛋糕分成两块，横着切一刀也会将蛋糕分成两块。因此，可以枚举第一刀的位置，再递归求解剩下的部分，得到最大蛋糕面积的下限。具体地，可以使用两个变量 i 和 k，其中 i 表示第一刀的位置，k 表示前 k 刀已经切好了，剩下的 m-1-k 刀还未切。则切下来的蛋糕面积为 w * i 或 h * i ，剩下的蛋糕面积为 (w - i) * h 或 w * (h - i) 。因此，递归求解得到的两个面积的较大值即为当前状态的最大蛋糕面积下限。

3. 基础情况

当 w * h < m+1 时，无法分出 m+1 块蛋糕，返回正无穷表示无法分割。当 m=0 时，说明已经切好了，返回当前蛋糕的面积。

4. 记忆化搜索

为了避免重复计算，可以使用记忆化搜索来保存已经求解过的状态，遇到重复状态时直接返回已经计算好的结果。

5. 递归返回值

最终递归返回的值为 ways[w][h][m]，即当前状态的最大蛋糕面积下限。

综上所述，该递归算法通过不断地切割蛋糕，并记录当前状态的最大蛋糕面积下限来求解问题，实现了记忆化搜索，同时也避免了重复计算，提高了程序的效率。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <vector>
 7 #include <map>
 8 #include <stack>
 9 #include <queue>
10 #include <deque>
11 #include <list>
12 #include <set>
13 #include <cctype>
14 
15 using namespace std;
16 
17 inline int read(int &s)
18 {
19     s = 0;
20     int w = 1;
21     char ch = getchar();
22     while (ch < '0' || ch > '9')
23     {
24         if (ch == '-')
25             w = -1;
26         ch = getchar();
27     }
28     while (ch >= '0' && ch <= '9')
29     {
30         s = s * 10 + ch - '0';
31         ch = getchar();
32     }
33     return s * w;
34 }
35 
36 inline void write(int x)
37 {
38     if (x < 0)
39     {
40         putchar('-');
41         x = -x;
42     }
43     if (x > 9)
44         write(x / 10);
45     putchar(x % 10 + '0');
46 }
47 
48 const int N = 30, INF = 0x3f3f3f3f;
49 int ways[N][N][N * N]; // 切法的记忆化搜索
50 // ways[w][h][m]表示当前蛋糕宽度为w，高度为h，已经切了m刀时，最大蛋糕的面积下限
51 
52 // 最大蛋糕的面积下限
53 int dfs(int w, int h, int m) // m为切的刀数
54 {
55     if (w * h < m + 1) // 分不出那么多块
56         return INF;
57     if (m == 0)
58         return w * h;        // 切好了
59     if (ways[w][h][m] != -1) // 记忆
60         return ways[w][h][m];
61 
62     int mincake = INF;
63     for (int i = 1; i < w; ++i)     // 第一刀是竖着切的，第一刀可以有 w - 1 个位置，i表示第一刀的位置
64         for (int k = 0; k < m; ++k) // k表示前k刀已经切好了，剩下的 m - 1 - k 刀还未切
65         {
66             int m1 = dfs(i, h, k);               // 切下来的蛋糕
67             int m2 = dfs(w - i, h, m - 1 - k);   // 剩下的蛋糕
68             mincake = min(mincake, max(m1, m2)); // m1, m2中较大值才是最大蛋糕的最小值
69         }
70 
71     for (int i = 1; i < h; ++i) // 第一刀是横着切的
72         for (int k = 0; k < m; ++k)
73         {
74             int m1 = dfs(w, i, k);
75             int m2 = dfs(w, h - i, m - 1 - k);
76             mincake = min(mincake, max(m1, m2));
77         }
78 
79     ways[w][h][m] = mincake;
80 
81     return ways[w][h][m];
82 }
83 
84 int main()
85 {
86     int w, h, m;
87     while (cin >> w >> h >> m && w != 0 && h != 0 && m != 0)
88     {
89         memset(ways, -1, sizeof(ways));
90         cout << dfs(w, h, m - 1) << endl;
91     }
92     // system("pause");
93     return 0;
94 }