【題目敘述】https://judge.tcirc.tw/ShowProblem?problemid=d082
【解題想法】DP
- dp[x1][y1][x2][y2] = 刪除子矩陣 (x1, y1) ~ (x2, y2) 的最小花費 (參考下圖例)。
- 狀態轉移方程：子矩陣扣除「邊緣一行」或「邊緣一列」後的「更小子矩陣」的花費，加上刪除「邊緣一行」或「邊緣一列」的花費。有四種可能性，取其中花費最小者。
- 枚舉所有子矩陣的起點 (i, j)，及所有合法的子矩陣大小，列數 rows，行數 cols。
- 函數 del_line(int x1, int y1, int x2, int y2)：計算刪除一行或一列的花費。
#include <iostream>
#include <algorithm>
using namespace std;
int R, C, ans;
int a[26][26];
int dp[26][26][26][26];
int del_line(int x1, int y1, int x2, int y2){
int zeros = 0, ones = 0;
for (int i=x1; i<=x2; i++){
for (int j=y1; j<=y2; j++){
zeros += (a[i][j] == 0);
ones += (a[i][j] == 1);
}
}
return min(zeros, ones);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
while (cin >> R >> C) {
for (int i=0; i<R; i++){
for (int j=0; j<C; j++){
cin >> a[i][j];
}
}
for (int rows=1; rows<R; rows++){
for (int cols=1; cols<C; cols++){
for (int i=0; i+rows<R; i++){
for (int j=0; j+cols<C; j++){
dp[i][j][i+rows][j+cols] = min({
dp[i+1][j][i+rows][j+cols] + del_line(i, j, i, j+cols),
dp[i][j+1][i+rows][j+cols] + del_line(i, j, i+rows, j),
dp[i][j][i+rows-1][j+cols] + del_line(i+rows, j, i+rows, j+cols),
dp[i][j][i+rows][j+cols-1] + del_line(i, j+cols, i+rows, j+cols)
});
}
}
}
}
cout << dp[0][0][R-1][C-1] << '\n';
}
return 0;
}