题解归档 - cf2225C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2225C
• 本地来源：problems/cf2225C/idea.md
• 题目链接：https://codeforces.com/contest/2225/problem/C
• 原始标题：cf2225C - Red-Black Pairs

思路

cf2225C - Red-Black Pairs

A valid final grid must admit a domino tiling where each domino has one color.

For a 2 x n board, every tiling is composed of:

• one vertical domino in a column; or
• two horizontal dominoes covering two adjacent columns.

Cost:

• Vertical at column i: repaint one cell iff top[i] != bottom[i].
• Horizontal block (i, i+1): repaint top pair iff top[i] != top[i+1], and same for bottom.

DP:

• dp[i] = minimum repaint cost for the first i columns.
• dp[i+1] = min(dp[i+1], dp[i] + vertical(i))
• dp[i+2] = min(dp[i+2], dp[i] + horizontal(i,i+1))

Answer: dp[n].

Check:

• Brute recursively enumerates all domino tilings for small n.

代码

来源：problems/cf2225C/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n;
        string a,b;
        cin>>n>>a>>b;
        const int INF=1e9;
        vector<int>dp(n+1,INF);
        dp[0]=0;
        for(int i=0;i<n;i++){
            int vertical=(a[i]!=b[i]);
            dp[i+1]=min(dp[i+1],dp[i]+vertical);
            if(i+1<n){
                int horizontal=(a[i]!=a[i+1])+(b[i]!=b[i+1]);
                dp[i+2]=min(dp[i+2],dp[i]+horizontal);
            }
        }
        cout<<dp[n]<<"\n";
    }
    return 0;
}