题解：P12211 [蓝桥杯 2023 国 Python B] 翻转
czh1005
·
·
题解
这道题很明显是 dp，最开始想的是一维状态。 \
但发现这样子就不知道上一个字符串翻没翻转。\
所以加一个维度。\
$dp_{i,0/1}$ 表示前 $i$ 个字符串拼起来，如果是 $0$ 表示第 $i$ 个字符串不进行翻转，如果是 $1$ 表示第 $i$ 个字符串进行翻转的最小长度。\
每个字符串用 $a_{i}$，$b_{i}$ 表示。\
转移方程：\
$$dp_{i,0} \gets \min(dp_{i-1,0}+2-[b_{i-1}=a_{i}],dp_{i-1,1}+2-[a_{i-1}==a_{i}])$$\
$$dp_{i,1} \gets \min(dp_{i-1,0}+2-[b_{i-1}=b_{i}]),dp_{i-1,1}+2-[a_{i-1}==b_{i}])$$\
代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,dp[maxn][2];
char a[maxn],b[maxn];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
dp[1][0]=dp[1][1]=2;//初始化
for(int i=1;i<=n;i++){
//转移方程
dp[i][0]=min(dp[i-1][0]+(b[i-1]==a[i]?1:2),
dp[i-1][1]+(a[i-1]==a[i]?1:2));
dp[i][1]=min(dp[i-1][0]+(b[i-1]==b[i]?1:2),
dp[i-1][1]+(a[i-1]==b[i]?1:2));
}
cout<<min(dp[n][0],dp[n][1])<<'\n';//输出答案
return 0;
}
```