Bài này được giải bằng quy hoạch động kết hợp đệ quy có nhớ. Ta gọi mảng ~dp[w][h][num]~ với ~w, h~ là kích thước thanh sô-cô-la và ~num~ là số ô vuông cần để ăn.

Công thức

• Nếu ~w.h < num~ thì ~dp[w][h][num] = inf~.
• Nếu ~w.h = num~ hoặc ~num = 0~ thì ~dp[w][h][num] = 0~.
• Ta duyệt ~c~ là số ô vuông sẽ ăn ở một trong hai phần, phần còn lại sẽ cần ~num-c~ ô vuông để ăn.
  • Nếu cắt theo chiều dọc, ~dp[w][h][num] = min(dp[i][h][c] + dp[w-i][h][num-c] + h^2)~ (với ~i~ là vị trí cắt, ~1 \le i \le w-1~);
  • Nếu cắt theo chiều ngang, ~dp[w][h][num] = min(dp[w][j][c] + dp[w][h-j][num-c] + w^2)~ (với ~j~ là vị trí cắt, ~1 \le j \le h-1~).

Độ phức tạp

Xấp xỉ ~O(n^3k^2)~.

Code tham khảo

// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
typedef long long ll;

const int N = 31, K = 51;
ll dp[N][N][K];
int n, m, k;
const ll INF = 1e18;

void Input() {
    cin >> n >> m >> k;
}

ll DP(int w, int h, int cnt) {
    ll &res = dp[w][h][cnt];
    if (~res) return res;
    if (w*h < cnt) return res = INF;
    if (cnt == 0 || w*h == cnt) return res = 0;

    res = INF;
    FOR(c1, 0, cnt) {
        FOR(i, 1, w-1) {
            res = min(res, DP(i, h, c1) + DP(w-i, h, cnt-c1) + h*h);
        }
        FOR(j, 1, h-1) {
            res = min(res, DP(w, j, c1) + DP(w, h-j, cnt-c1) + w*w);
        }
    }
    return res;
}

void Solve() {
    cout << DP(n, m, k) << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    memset(dp, -1, sizeof dp);
    int t; cin >> t;
    while (t--)
        Input(), Solve();
    return 0;
}