POJ 2951 - Cake Cutting

http://poj.org/problem?id=2951

概要

\(w \times h\) の長方形がある． 1つの長方形を水平方向か垂直方向に切るという操作を \(m-1\) 回繰り返す． その後の \(m\) 個の長方形の面積の最大値を最小化した値を答える．

制約

• \(1 \le w, h, m \le 20\)
• \(m \le w h\)

解法

状態数は \(20^3\) 程度しかないので，メモ化再帰で求める． 値の更新に \(20^2\) 程度かかるので，全体で \(20^5\) 程度になる．

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int memo[21][21][21];
 6 
 7 int solve(int W, int H, int M)
 8 {
 9   if (W > H) {
10     swap(W, H);
11   }
12   int& ans = memo[W][H][M];
13   if (ans != 0) {
14     return ans;
15   } else if (M == 1) {
16     ans = W*H;
17     return ans;
18   } else {
19     ans = W*H;
20     for (int i = 1; i < W; i++) {
21       for (int j = 1; j < M; j++) {
22         const int x = solve(i, H, j);
23         const int y = solve(W-i, H, M-j);
24         ans = min(ans, max(x, y));
25       }
26     }
27     for (int i = 1; i < H; i++) {
28       for (int j = 1; j < M; j++) {
29         const int x = solve(W, i, j);
30         const int y = solve(W, H-i, M-j);
31         ans = min(ans, max(x, y));
32       }
33     }
34     return ans;
35   }
36 }
37 
38 int main()
39 {
40   int W, H, M;
41   while (cin >> W >> H >> M && M != 0) {
42     cout << solve(W, H, M) << endl;
43   }
44   return 0;
45 }