算法
(动态规划) $O(HW)$
记 dp[i][j][x][y]
表示当我们走到方格 $(i, j)$ 时, 已将第 $i$ 行翻转 $x$ 次、第 $j$ 行翻转 $y$ 次的最小费用
由于走到方格 $(i, j)$ 时,可以选择翻转第 $i$ 行也可以不翻转第 $i$ 行,所以此时第 $i$ 行可以翻转 $0$ 次或 $1$ 次;类似地,此时第 $j$ 列可以翻转 $0$ 次或 $1$ 次
于是我们可以令 $k = 2y+x$ 将行列的翻转情况进行合并
C++ 代码
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
inline void chmin(ll& x, ll y) { if (x > y) x = y; }
ll dp[2005][2005][4];
int main() {
int h, w;
cin >> h >> w;
vector<int> r(h), c(w);
rep(i, h) cin >> r[i];
rep(i, w) cin >> c[i];
vector<string> a(h);
rep(i, h) cin >> a[i];
const ll INF = 1e18;
rep(i, h)rep(j, w)rep(k, 4) dp[i][j][k] = INF;
rep(k, 4) {
ll co = 0;
if (k&1) co += r[0];
if (k&2) co += c[0];
dp[0][0][k] = co;
}
rep(i, h)rep(j, w)rep(k, 4) {
int x = a[i][j]-'0';
if (k&1) x ^= 1;
if (k&2) x ^= 1;
if (i+1 < h) { // 从上到下时只能翻转行
int nk = k&2, y = a[i+1][j]-'0';
if (k&2) y ^= 1;
ll co = 0;
if (x != y) co += r[i+1], nk |= 1;
chmin(dp[i+1][j][nk], dp[i][j][k]+co);
}
if (j+1 < w) { // 从左到右时只能翻转列
int nk = k&1, y = a[i][j+1]-'0';
if (k&1) y ^= 1;
ll co = 0;
if (x != y) co += c[j+1], nk |= 2;
chmin(dp[i][j+1][nk], dp[i][j][k]+co);
}
}
ll ans = INF;
rep(k, 4) chmin(ans, dp[h-1][w-1][k]);
cout << ans << '\n';
return 0;
}