【題解】ZeroJudge d053: 10970 – Big Chocolate

【題目敘述】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)
分享本文 Share with friends