题解：CF2225C Red-Black Pairs
chenyuze_2029
·
·
题解
很裸的一个 dp。
给你一个 $2\times n$ 的矩阵，每个格子有一个颜色 `R` 或 `B`。你需要将这 $n\times2$ 个格子两两配对，使配对的两个格子相邻并且颜色相同。问至少改变多少个格子的颜色才能存在一组可能的配对方案。
发现前面的格子怎么配对不会影响后面的格子，满足无后效性。考虑 dp。
设 $f_i$ 表示前 $i$ 列的格子全部配对完的最小花费。
:::success[为什么可以一列一列的配对]
如果不是一列一列配对的话，就只有如下这种情况：
```
?BB
RR?
```
如果我们像上面一样配对的话，左边剩下的和右边剩下的都是奇数个，无法全部配对。所以同一列的格子一定是相互配对或并排配对的。
:::
我们按照一列或两行的配对来转移：
1. 如果到第 $i$ 列要竖着配对，则判断这一列的格子颜色是否相同即可。如果不同则需要付出 $1$ 的花费。状态转移方程为 $f_i\leftarrow f_{i-1}+[a_{1,i}\neq a_{2,i}]$。
2. 如果到第 $i$ 列要横着配对，则需要分别判断第 $1$ 行两个格子是否同色，第 $2$ 行两个格子是否同色即可。状态转移方程为 $f_i\leftarrow f_{i-2}+[a_{1,i-1}\neq a_{1,i}]+[a_{2,i-1}\neq a_{2,i}]$。
答案即为 $f_n$。
:::success[[$\text{\color{green}Accepted code}$](https://codeforces.com/contest/2225/submission/372088438)]
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x;cin>>x;return x;}
void write(int x){cout<<x;}
const int N=1000002;
int t,n,a[4][N],f[N];
inline void work()noexcept
{
n=read();
for(int i=1;i<=n;i=-~i)
{
char ch;
cin>>ch;
a[1][i]=(ch=='R'?1:0),f[i]=0;
}
for(int i=1;i<=n;i=-~i)
{
char ch;
cin>>ch;
a[2][i]=(ch=='R'?1:0);
}
f[0]=0;
for(int i=1;i<=n;i=-~i)
{
if(a[1][i]==a[2][i])f[i]=f[i-1];
else f[i]=f[i-1]+1;
if(i!=1)
{
int sum=f[i-2];
if(a[1][i]!=a[1][i-1])sum++;
if(a[2][i]!=a[2][i-1])sum++;
f[i]=min(f[i],sum);
}
}
write(f[n]),putchar('\n');
}
signed main()
{
t=read();
while(t--)work();
return 0;
}
```
~~你发现上面的 AC 能点了吗。~~
:::