题解：P14347 [JOISC 2019] 灯 / Lamps

· · 题解

怎么没有人发题解啊，我来写一发。

以下称第三种操作为“翻转”，第一二种操作均为“推平”。

对于推平操作，它们分别互不相交，这个十分显然。

而对于翻转操作，有如下结论：

  1. 翻转区间操作之间可以转换成互不相交的翻转区间。
  2. 翻转和推平操作相交则可以先推平再翻转。

对于第一个结论，翻转区间本质上就是将区间异或上 1，而众所周知异或 1 两次相当于没变，若两个翻转区间相交，则相交的部分会被异或两次不变，仅没相交的部分翻转了，于是转换成了两个不相交区间。

对于第二个结论，若包含：假设原推平为 1，那也可以先推平为 0，再全部翻转；若部分交，则直接转化为不相交，所以先推平再反转不劣。

故我们可以设计出转移方程：设 dp_{i,0} 表示将第 i 盏灯推平成 0 的操作次数，dp_{i,1} 表示将第 i 盏灯推平成 1 的操作次数，dp_{i,2} 表示保持原先状态不变的操作次数，然后分目标串的状态讨论即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int dp[N][3],n;
//dp[i][0/1/2]表示第i盏灯推平成0/推平成1/不变的操作次数 
string s,t;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>s>>t;
    s=" "+s;t=" "+t;
    dp[1][0]=1+(t[1]=='1');
    dp[1][1]=1+(t[1]=='0');
    dp[1][2]=(s[1]!=t[1]);
    for(int i=2;i<=n;i++){
        if(t[i]=='1'){
            dp[i][0]=min(dp[i-1][0]+(t[i-1]=='0'),
            min(dp[i-1][1]+(t[i-1]=='1')+1,dp[i-1][2]+(s[i-1]==t[i-1])+1));
            //上一位置 0，不用重新推平，上一个不用反转，这一位额外反转 
            //上一位置 1，需要重新推平，上一位不用反转，这一位额外反转 
            //上一位不变，需要重新推平，上一位不用反转，这一位额外反转 
            dp[i][1]=min(dp[i-1][0]+1,min(dp[i-1][1],dp[i-1][2]+1));
            //上一位置 0，需要重新推平，这一位不用反转，不管 
            //上一位置 1，不用重新推平 
            //上一位不变，需要重新推平 
            dp[i][2]=min(dp[i-1][0]+(t[i-1]=='0'&&s[i]!=t[i]),
            min(dp[i-1][1]+(t[i-1]=='1'&&s[i]!=t[i]),dp[i-1][2]+(s[i-1]==t[i-1]&&s[i]!=t[i])));
            //这一位不变，不用重新推平，只看这一位和上一位需不需要反转 
        }
        else{//同理 
            dp[i][0]=min(dp[i-1][0],min(dp[i-1][1]+1,dp[i-1][2]+1));
            dp[i][1]=min(dp[i-1][0]+(t[i-1]=='0')+1,
            min(dp[i-1][1]+(t[i-1]=='1'),dp[i-1][2]+(s[i-1]==t[i-1])+1));
            dp[i][2]=min(dp[i-1][0]+(t[i-1]=='0'&&s[i]!=t[i]),
            min(dp[i-1][1]+(t[i-1]=='1'&&s[i]!=t[i]),dp[i-1][2]+(s[i-1]==t[i-1]&&s[i]!=t[i])));
        }
    } 
    cout<<min(dp[n][0],min(dp[n][1],dp[n][2]))<<"\n";
    return 0;
}