【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d053
【解題想法】Divide & Conquer
【方法-1】數值解
- 先沿著 n 方向切成 n 條長條 (寬度為 1，長度為 m)，總共切 n – 1 刀。
- 接著每一條長條（有 n 條）都要再切 (m – 1)刀。
- 答案 = n – 1 + n * (m – 1) = n * m – 1。
#include <iostream>
using namespace std;
int main() {
int M, N;
while (cin >> M >> N) {
//n - 1 + n * (m - 1)
cout << M * N - 1 << "\n";
}
}
【方法-2】分治法 + 記憶化 (DP)
- a[x][y]：一塊 x * y 的巧克力最少需切幾刀。（初始值 -1）
- 因為先切哪一邊結果都一樣，只要 x > 1，就先切 x 方向。否則改切 y 方向。
- 記住已經算過的答案，且 a[x][y] = a[y][x]。
#include <iostream>
#include <cstring>
using namespace std;
int n, m, a[305][305];
int solve(int x, int y) {
if (a[x][y] != -1) return a[x][y];
if (x > 1) a[x][y] = solve(x-1, y) + solve(1, y) + 1;
else a[x][y] = solve(x, y-1) + solve(x, 1) + 1;
a[y][x] = a[x][y];
return a[x][y];
}
int main() {
memset(a, -1, sizeof(a));
a[1][1] = 0;
while (cin >> n >> m) {
cout << solve(n, m) << "\n";
}
}
Python code (credit: Amy Chou)
import sys
for line in sys.stdin.readlines():
M, N = map(int, line.split())
print(M * N - 1)