Hướng dẫn giải của Thanh sô-cô-la
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
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;
}
Bình luận