「JOISC2019」开关游戏

发表于 | 更新于 | 分类于 | 阅读次数：

题意简述

LOJ 3037

一列灯 $n$ 个，给定初始状态和目标状态。
每次操作可以区间开启/关闭/取反，求最少操作次数从初始状态变为目标状态。
$n\le 10^6$。

主要思路

注意到若相邻两个是先区间反转再区间赋值，可以简单地通过一些变换使得把两者顺序调换。
那么必然存在一个最优操作序列，使得前面全为区间赋值，后面都是区间反转；同时可以有区间赋值操作互不相交。
设 $f(i, [0, 2])$ 为处理到第 $i$ 盏灯，钦定这盏灯被赋值为0/1/2(未被赋值)，此时需要的区间反转次数的两倍。
简单 dp 即可。

参考代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define Templ(T) template <typename T>
#define gcr() getchar()
inline int read() {
    reg int ans = 0, f = 1;
    reg char c = gcr();
    while (!isdigit(c)) f ^= (c == '-'), c = gcr();
    for (; isdigit(c); c = gcr()) ans = (ans << 1) + (ans << 3) + (c ^ 48);
    return f ? ans : -ans;
}
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
} // namespace my_std
using namespace my_std;

const int N = 1000010, tr[3][3] = {
    {0, 2, 1},
    {2, 0, 1},
    {1, 1, 0}
};
int n;
char a[1 << 20], b[1 << 20];

void read_line(char *a){
    for(*a = gcr(); *a != 48 && *a != 49; *a = gcr());
    for(; *a == 48 || *a == 49; *++a = gcr());
}
int f[1 << 20][3];

#define val(x, o) ((o) & 2 ? (a[x] ^ b[x]) : ((o) ^ b[x] ^ 48))

int main(){
    n = read();
    read_line(a), read_line(b);
    a[n] = b[n] = 48;
    memset(f, 0x3f, sizeof(f));
    f[0][2] = *a ^ *b;
    f[0][0] = 1 + (*b ^ 48);
    f[0][1] = 1 + (*b ^ 49);
    FOR(i, 1, n) FOR(k, 0, 2){
        FOR(j, 0, 2){
            chkmin(f[i][k], f[i - 1][j] + tr[j][k] + (val(i, k) ^ val(i - 1, j)));
        }
    }
    printf("%d\n", f[n][2] >> 1);
    return 0;
}