Gọi dp[i][j] là số lần cắt hình chữ nhật có chiều dài i và chiều rộng j thành các hình vuông. Ta có hệ thức truy hồi như sau:
- Nếu i = j, hình này là hình vuông, không cần cắt. Do đó dp[i][j] = 0;
- Nếu i != j, ta thực hiện chia hình như sau:
- Kẻ 1 đoạn thẳng song song với chiều rộng, chia chiều dài thành 2 phần k và i - k. Khi đó dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k][j] + 1);
- Tương tự, kẻ 1 đoạn thẳng song song với chiều dài, chia chiều rộng thành 2 phần k và j - k. Khi đó dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j - k] + 1);
Kết quả cuối cùng sẽ là dp[a][b]
```cpp
#include <iostream>
#include <vector>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int a, b;
std::cin >> a >> b;
std::vector<std::vector<int>> dp(a + 1, std::vector<int>(b + 1, 1e9));
for (int i = 1; i <= a; ++i) {
for (int j = 1; j <= b; ++j) {
if (i == j) {
dp[i][j] = 0;
continue;
}
for (int k = 1; k < i; ++k) dp[i][j] = std::min(dp[i][j], dp[k][j] + dp[i - k][j] + 1);
for (int k = 1; k < j; ++k) dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[i][j - k] + 1);
}
}
std::cout << dp[a][b];
}
aviciier
Created at
0 likes