做法
简单的 DP。
很容易想到，对于一个 $2 \times 2$ 的部分只有两种填法：
很显然可以 DP 吧？
设 $dp[i]$ 表示前 $i$ 列满足要求的最小代价。
然后位置 $i$ 可以由 $i-2$ 通过加两个横着的矩形转移（填充方法 $1$），也可以由 $i-1$ 用过加一个竖着的矩形转移（填充方法 $2$ 取一半）。
用字符串 $a, b$ 代表第一、第二行，那么转移：
dp[i] = min(dp[i - 1] + (a[i] != b[i]), dp[i - 2] + (a[i] != a[i - 1]) + (b[i] != b[i - 1]));
Code
#include <bits/stdc++.h>
#define ll long long
#define str string
#define db double
using namespace std;
constexpr ll MAXN = 2e5 + 5;
ll t, n, dp[MAXN];
str a, b;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> t;
while (t--) {
cin >> n >> a >> b;
a = ' ' + a, b = ' ' + b, dp[0] = 0;
for (ll i = 1; i <= n; ++i) {
dp[i] = dp[i - 1] + (a[i] != b[i]);
if (i >= 2)
dp[i] = min(dp[i], dp[i - 2] + (a[i] != a[i - 1]) + (b[i] != b[i - 1]));
}
cout << dp[n] << '\n';
}
return 0;
}
说些什么吧！