题解：CF2225C Red-Black Pairs

DrDuck · 2026-04-26 16:15:14 · 题解

砖头 dp（指转移方程像一块砖的 dp）。

设 f_{i,0/1/2,0/1/2} 为考虑前 i 列，第 i 列上面那块砖分别为红色且为配对，黑色且未配对，已配对，下面那块砖同理的方案数。

下面列举几种转移分析，同理的具体转移见代码。

• 要求 f_{i,0,1}，那么前面那一列一定不能有未配对的砖，从 f_{i-1,2,2} 转移过来，f_{i,1,0} 同理。
• 要求 f_{i,0,2}，那么前面那一列上面那块砖一定已配对，下面那块砖的颜色有两种情况，从 f_{i-1,2,0} 和 f_{i-1,2,1} 转移过来。f_{i,1,2},f_{i,2,0},f_{i,2,1} 同理。
• 要求 f_{2,2}，要么是这一类上下两块砖相互配对，要么是和前面的砖配对，从 f_{i-1,2,2},f_{i-1,0,1},f_{i-1,1,0} 转移过来。

状态为 f_{i,0,0} 和 f_{i,1,1} 没有意义，因为可以互相配对转化为 f_{i,2,2}。

:::success[CODE] 虽然代码看上去吓人，但是我因为砖头 dp 做的比较多，十二分钟就打完调完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e+5 + 5, inf = 1e17;
int T, n;
int f[maxn][3][3], a[maxn], b[maxn];
void GOGOGO() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        a[i] = c == 'R' ? 0 : 1;
    }
    for (int i = 0; i <= n; i++) memset(f[i], 0x3f, sizeof(f[i]));
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        b[i] = c == 'R' ? 0 : 1;
    }
    f[0][2][2] = 0;
    for (int i = 1; i <= n; i++) {
        f[i][0][1] = f[i - 1][2][2] + (a[i] ^ 0) + (b[i] ^ 1);
        f[i][1][0] = f[i - 1][2][2] + (a[i] ^ 1) + (b[i] ^ 0);
        f[i][0][2] = min(f[i - 1][2][0] + (b[i] ^ 0), f[i - 1][2][1] + (b[i] ^ 1)) + (a[i] ^ 0);
        f[i][1][2] = min(f[i - 1][2][0] + (b[i] ^ 0), f[i - 1][2][1] + (b[i] ^ 1)) + (a[i] ^ 1);
        f[i][2][0] = min(f[i - 1][0][2] + (a[i] ^ 0), f[i - 1][1][2] + (a[i] ^ 1)) + (b[i] ^ 0);
        f[i][2][1] = min(f[i - 1][0][2] + (a[i] ^ 0), f[i - 1][1][2] + (a[i] ^ 1)) + (b[i] ^ 1);
        f[i][2][2] = min({f[i - 1][2][2] + min((a[i] ^ 0) + (b[i] ^ 0), (a[i] ^ 1) + (b[i] ^ 1)), f[i - 1][0][1] + (a[i] ^ 0) + (b[i] ^ 1), f[i - 1][1][0] + (a[i] ^ 1) + (b[i] ^ 0)});
    }
    cout << f[n][2][2] << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T--) GOGOGO();
    return 0;
}

:::