题解：P5924 [IOI2004] Phidias 菲迪亚斯神
Begemot
·
·
题解
枚举每块矩形可以划分成的两块子矩形，用子矩形的和的最小值更新 $f_{i,j}$。
因为可以横着划分也可以竖着划分，所以时间复杂度为 $O(W\cdot H\cdot(W+H))$。
代码：
```cpp
#include <iostream>
const int MAXN = 605;
using namespace std;
int w, h, n;
int f[MAXN][MAXN];
int main() {
ios::sync_with_stdio(false);
cin >> w >> h;
for (int i = 1; i <= w; ++i) {
for (int j = 1; j <= h; ++j) {
f[i][j] = i * j;
}
}
cin >> n;
for (int i = 1; i <= n; ++i) {
int wi, hi;
cin >> wi >> hi;
f[wi][hi] = 0;
}
for (int i = 1; i <= w; ++i) {
for (int j = 1; j <= h; ++j) {
for (int k = 1; k <= i; ++k) {
f[i][j] = min(f[i][j], f[k][j] + f[i - k][j]);
}
for (int k = 1; k <= j; ++k) {
f[i][j] = min(f[i][j], f[i][k] + f[i][j - k]);
}
}
}
cout << f[w][h] << endl;
return 0;
}
```