题解：CF2181M Medical Parity

· · 题解

题目大意

给定两个长度为 n 的二进制串 x' 和 y' ，每次可以翻转任意一个位置（在任意一个串中）。要求最少修改次数，使得存在某个 x, y ，满足：

思路

dp[i][1]表示前i个字符，y的结尾为1的最优解
dp[i][0]表示前i个字符，y的结尾为0的最优解

然后就很容易推出状态转移方程：

if(x[i]=='0' && y[i]=='0'){//x[i]结尾为1，y[i]结尾也为1
    dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1);//可以由dp[i-1][0]与dp[i-1][1]转移过来
    dp[i][1]=dp[i-1][1]+1;//只能由dp[i-1][1]转移过来(题目中说明了在同一个位置中x与至多只能改变一个)
}
    if(x[i]=='0' && y[i]=='1'){
        dp[i][0]=dp[i-1][0]+1;
        dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1);
    }
    if(x[i]=='1' && y[i]=='0'){
        dp[i][0]=min(dp[i-1][1],dp[i-1][0]+1);
        dp[i][1]=dp[i-1][0]+1;
    }
    if(x[i]=='1' && y[i]=='1'){
        dp[i][0]=dp[i-1][1]+1;
        dp[i][1]=min(dp[i-1][0],dp[i-1][1]+1);
    }

后面几个比较绕，可以自己多推一推。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
int t,dp[N][2];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        string x,y;
        cin>>x>>y;
        int ans,n=x.size();
        x=" "+x;
        y=" "+y;
        dp[0][1]=1e9;
        //dp[0][1]是不可能实现的，所以赋了个极大值
        for(int i=1;i<=n;i++){
            if(x[i]=='0' && y[i]=='0'){
                dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1);
                dp[i][1]=dp[i-1][1]+1;
            }
            if(x[i]=='0' && y[i]=='1'){
                dp[i][0]=dp[i-1][0]+1;
                dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1);
            }
            if(x[i]=='1' && y[i]=='0'){
                dp[i][0]=min(dp[i-1][1],dp[i-1][0]+1);
                dp[i][1]=dp[i-1][0]+1;
            }
            if(x[i]=='1' && y[i]=='1'){
                dp[i][0]=dp[i-1][1]+1;
                dp[i][1]=min(dp[i-1][0],dp[i-1][1]+1);
            }
        }
        cout<<min(dp[n][1],dp[n][0])<<"\n";
    }
    return 0;
}

完结撒花