题解：P14347 [JOISC 2019] 灯 / Lamps

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

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

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

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

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

对于第一个结论，翻转区间本质上就是将区间异或上

1

，而众所周知异或

1

两次相当于没变，若两个翻转区间相交，则相交的部分会被异或两次不变，仅没相交的部分翻转了，于是转换成了两个不相交区间。

对于第二个结论，若包含：假设原推平为

1

，那也可以先推平为

0

，再全部翻转；若部分交，则直接转化为不相交，所以先推平再反转不劣。

故我们可以设计出转移方程：设

dp_{i,0}

表示将第

i

盏灯推平成

0

的操作次数，

dp_{i,1}

表示将第

i

盏灯推平成

1

的操作次数，

dp_{i,2}

表示保持原先状态不变的操作次数，然后分目标串的状态讨论即可。

CPP

#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;
}

题解：P14347 [JOISC 2019] 灯 / Lamps

文章操作

相关推荐

评论

题解：P14347 [JOISC 2019] 灯 / Lamps