JOISC 2019 Day3 开关游戏 题解

First Post:

Last Update:

一道比较规整的最优化题。

首先,因为 OFF/ON 又会覆盖掉之前的影响,也就是说,在 OFF/ON 之前做的 TOG 操作可能被覆盖掉而白费力气,所以,所有的 TOG 操作都在 OFF/ON 之后一定不劣。

那我们先考虑,如果只做 OFF/ON 操作,怎么找到最优次数。

我们可以先不管序列 怎么样,只根据序列 的形态找到一个答案上界。事实上,序列 中一段连续的相等数可以缩为一个。如果缩完之后形如 ,那就需要 的个数那么多次操作,如果形如 ,那就需要 的个数再加 。总而言之,就是

那么序列 有什么用呢?对于 的位置,我们可以将其左边和右边分成两部分来处理,也可以不分。按照这些位置分完部分(注意这个部分与上文的"连续段"是不同的概念)后,直接套用上述结论即可得到最优次数。

那么 TOG 操作怎么处理?其实是简单的,因为 TOG 操作肯定最后进行,且 TOG 操作是可逆的,所以完全可以看作:对序列 进行 TOG 操作。

因为决策还是有点复杂,考虑设计 DP 状态 ,表示 DP 到前 位,第二维表示当前处于一个以 开头的部分中,或用 表示不处于任何一个部分中, 表示当前位有没有被 TOG 操作覆盖。转移是简单的,分类讨论即可,时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
template<typename T> inline bool ckmin(T &x,const T &y) { return (y < x) && (x = y,true);}
int n,a[N],b[N];
string str;
int dp[N][3][2];
int main() {
cin >> n;
cin >> str;
for(int i = 1;i <= n;i++) a[i] = str[i - 1] - '0';
cin >> str;
for(int i = 1;i <= n;i++) b[i] = str[i - 1] - '0';
memset(dp,0x3f,sizeof dp);
dp[0][2][0] = 0;
for(int i = 1;i <= n;i++)
for(int rv = 0;rv < 2;++rv)
for(int lv = 0;lv < 2;++lv) {
int tb = b[i] ^ rv,lb = b[i - 1] ^ lv;
ckmin(dp[i][0][rv],dp[i - 1][0][lv] + (lb == 1 && tb == 0) + (lv == 0 && rv == 1));
if(tb == 0) ckmin(dp[i][0][rv],dp[i - 1][2][lv] + 1 + (lv == 0 && rv == 1));
ckmin(dp[i][1][rv],dp[i - 1][1][lv] + (lb == 0 && tb == 1) + (lv == 0 && rv == 1));
if(tb == 1) ckmin(dp[i][1][rv],dp[i - 1][2][lv] + 1 + (lv == 0 && rv == 1));
if(a[i] == tb)
ckmin(dp[i][2][rv],min({dp[i - 1][0][lv] + (lb != 0),dp[i - 1][1][lv] + (lb == 0),dp[i - 1][2][lv]}) + (lv == 0 && rv == 1));
}
int ans = 1e9;
for(int a = 0;a < 3;a++) for(int t = 0;t < 2;t++) ckmin(ans,dp[n][a][t] + (a < 2 ? (b[n] ^ t) != a : 0));
cout << ans << endl;
return 0;
}