思路
状态机 DP $O(n)$
用 $f(i, j)$ 表示状态机经过了前 $i$ 个字符,且最后两个字母被使用的状态是 $j$ 的所有方案中包含的最大子串数。其中,$j$ 的取值和含义如下表:
取值 | 含义 |
---|---|
0 | 最后两个字母是 00 ,且它们会组合在一起构成子串 |
1 | 最后两个字母是 x0 ,且它们不组合在一起构成子串 |
2 | 最后两个字母是 11 ,且它们会组合在一起构成子串 |
3 | 最后两个字母是 x1 ,且它们不组合在一起构成子串 |
状态之间的转换关系在代码注释中给出。
"""
0: '(00)'
'0' -> 1
'1' -> 3
1: 'x|0'
'0' -> 0, 1
'1' -> 3
2: '(11)'
'0' -> 1
'1' -> 3
3: 'x|1'
'0' -> 1
'1' -> 2, 3
"""
s = input()
n = len(s)
f = [[0] * 4 for _ in range(n)]
for i in range(1, n):
if s[i] != '1':
f[i][0] = f[i - 1][1] + (s[i - 1] != '1')
f[i][1] = max(f[i - 1])
if s[i] != '0':
f[i][2] = f[i - 1][3] + (s[i - 1] != '0')
f[i][3] = max(f[i - 1])
print(max(f[n - 1]))
贪心 $O(n)$
如果 $s[i - 1], s[i]$ 能够配对,则让它们配对一定能取到最优解。证明:仅证 $00$ 配对,其它配对方式同理。
若 $s[i - 1, i] = 00$,则对于任意一个 $s[i - 1], s[i]$ 不配对的方案,将它们改为配对,结果不会变差:
- 若 $s[i + 1], s[i]$ 会配对,则将它们拆开并让 $s[i - 1], s[i]$ 配对,子串数不变。
- 若 $s[i + 1], s[i]$ 不配对,则让 $s[i - 1], s[i]$ 配对,子串数加一。
因此,只要让 $s[i - 1], s[i]$ 配对(如果可以的话),一定能取到最优解。
s = input()
n = len(s)
res, i = 0, 1
while i < n:
a, b = s[i - 1], s[i]
if a == b or a == '?' or b == '?':
res += 1
i += 1
i += 1
print(res)