考虑判断一个终止态是否可达。如果只有一个棋子连续段那一定可达;否则就存在 \(\ge 2\) 个连续段。此时把放棋子看成删除,那么限制就是如果删除一个孤立的棋子(两边没有棋子)且还有别的格子有棋子,这个棋子的颜色 异于其他连续段的两边棋子的颜色 。
设第一个被删的段(最后一个放棋子的段)的最后一个棋子颜色为 \(c\),记其补色为 \(c'\)。想删掉这个棋子就必须把其他连续段删成两边都是 \(c'\)。借这个机会可以把所有包含 \(c\) 的段都删除,剩下的段只会包含 \(c'\)。这样的段最多只有一个(多了就寄了),所以这个段就是最后被删除的段(第一个放棋子的段)。
可以发现删棋子和放棋子的方案是一一对应的,所以“存在一个合法的删棋子方案”就是“存在一个合法的放棋子方案”的充要条件。
考虑枚举 \(c\),那么根据以上讨论有如下限制:
- 第一个被删的段必须包含子序列 \(c\)。
- 最后被删的段 和它两边 必须包含子序列 \(c'c'\)。
- 其他段 和它两边 必须包含子序列 \(c'cc'\)。
考虑左边和右边扩充 \(3\) 位后大力 dp。设 \(f_{i,0/1,0/1}\) 表示钦定 \(i\) 不放棋子,当前是否存在 第一个被删的段 ,当前是否存在 最后被删的段 ,放棋子数量的最小值。转移大概是如果 \(i-1\) 不放棋子就是 \(f_{i,x,y} \gets f_{i-1,x,y}\),否则枚举 \(i-1\) 所在段的左端点,考虑这一段是第一个被删的段、最后被删的段还是其他段。
直接做是 \(O(n^2)\) 的,考虑优化。容易通过子序列自动机找到以 \(i-1\) 为右端点的第一个合法的左端点,并且发现能转移的点是一段前缀。分三类记一下前缀最小值即可。这样是 \(O(n)\) 的。
code
// Problem: F - 1D Kingdom Builder
// Contest: AtCoder - AtCoder Regular Contest 109
// URL: https://atcoder.jp/contests/arc109/tasks/arc109_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
int n, a[maxn], b[maxn], pre[maxn][2];
int f[maxn][2][2], fa[2], fb[2], fc[2][2];
char s[maxn], t[maxn];
inline int work(int c) {
mems(f, 0x3f);
mems(fa, 0x3f);
mems(fb, 0x3f);
mems(fc, 0x3f);
f[1][0][0] = 0;
for (int i = 2, ja = 1, jb = 1, jc = 1; i <= n; ++i) {
if (b[i]) {
continue;
}
while (pre[i + 1][c ^ 1] && ja <= pre[pre[i + 1][c ^ 1] - 1][c ^ 1]) {
for (int x = 0; x <= 1; ++x) {
fa[x] = min(fa[x], f[ja][0][x] - ja);
}
++ja;
}
while (jb < pre[i][c]) {
for (int x = 0; x <= 1; ++x) {
fb[x] = min(fb[x], f[jb][x][0] - jb);
}
++jb;
}
while (jc <= pre[pre[pre[i + 1][c ^ 1]][c]][c ^ 1]) {
for (int x = 0; x <= 1; ++x) {
for (int y = 0; y <= 1; ++y) {
fc[x][y] = min(fc[x][y], f[jc][x][y] - jc);
}
}
++jc;
}
// printf("i: %d %d %d %d\n", i, ja, jb, jc);
f[i][0][0] = min(f[i - 1][0][0], fc[0][0] + i - 1);
f[i][1][0] = min(f[i - 1][1][0], min(fc[1][0], fa[0]) + i - 1);
f[i][0][1] = min(f[i - 1][0][1], min(fc[0][1], fb[0]) + i - 1);
f[i][1][1] = min(f[i - 1][1][1], min({fc[1][1], fa[1], fb[1]}) + i - 1);
// printf("i: %d %d %d %d %d\n", i, f[i][0][0], f[i][1][0], f[i][0][1], f[i][1][1]);
}
return f[n][1][1];
}
void solve() {
scanf("%d%s%s", &n, s + 4, t + 4);
for (int i = 4; i <= n + 3; ++i) {
a[i] = (s[i] == 'b');
b[i] = (t[i] == 'o');
}
a[n + 4] = a[n + 5] = a[n + 6] = 1;
n += 6;
pre[1][0] = pre[1][1] = 0;
for (int i = 2; i <= n + 1; ++i) {
for (int j = 0; j <= 1; ++j) {
pre[i][j] = pre[i - 1][j];
}
pre[i][a[i - 1]] = i - 1;
}
int l = -1, r = -1;
for (int i = 1; i <= n; ++i) {
if (b[i]) {
if (l == -1) {
l = i;
}
r = i;
}
}
printf("%d\n", min({r - l + 1, work(0), work(1)}));
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest Builder Kingdomatcoder regular contest builder atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest 167 subsegments atcoder regular contest inversion atcoder regular contest