FLY ME TO THE MOON

宝宝题。

首先能发现操作一二的推平区间不交。如果两个推平区间有交，如果他们推平的颜色相同，直接合并为同一个更优，对于推平颜色不同的情况，如果一个区间包含另一个区间，那么可以把后者改为区间翻转，操作数不劣，否则两区间有交但不包含，容易发现先操作的区间完全可以不操作交集，移动区间端点到交集一侧不劣。故每个点只会至多被推平一次。

另一个简单的观察是区间翻转一定在推平之后，并且不会翻转两次。那么可以直接 dp。

记

f_{i,0/1/2,0/1}

表示当前操作完前缀，第

i

位受到的操作是先不推平或推平为

0/1

，接着不翻转/翻转。转移 trivial，每次只保留能让

a_i

变成

b_i

的操作状态。转移到下一位时更新操作的状态即可。

CPP

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 1e6 + 10;
int F[N][3][2], n; char A[N], B[N];
int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> n >> (A + 1) >> (B + 1);
	memset(F, 0x3f, sizeof F);
	F[1][2][0] = 0;
	for (int i = 1; i <= n; i ++) {
		for (int a = 0; a < 2; a ++) for (int b = 0; b < 2; b ++)
			F[i][a][b] = min(F[i][a][b], F[i][2][b]);
		for (int a = 0; a < 3; a ++) 
			F[i][a][1] = min(F[i][a][1], F[i][a][0]);
		for (int a = 0; a < 3; a ++) for (int b = 0; b < 2; b ++) {
			int t = A[i] - '0';
			if (a != 2) t = a;
			t ^= b;
			if (t != B[i] - '0') F[i][a][b] = 1e9;
		}
		for (int a = 0; a < 3; a ++) for (int b = 0; b < 2; b ++)
			F[i + 1][a][b] = F[i][a][b];
		for (int a = 0; a < 2; a ++) for (int b = 0; b < 2; b ++)
			F[i + 1][2][b] = min(F[i + 1][2][b], F[i][a][b] + 1);
		for (int a = 0; a < 3; a ++) for (int b = 0; b < 2; b ++)
			F[i + 1][a][0] = min(F[i + 1][a][0], F[i][a][b] + 1);
	}
	cout << F[n + 1][2][0] << "\n";
	return 0;
}

文章操作

相关推荐

评论

FLY ME TO THE MOON