小红拿到了一个仅由数字字符组成的字符串。她准备选择一个非空子序列,使得该子序列中不包含连续的"61"子串。 小红想知道,有多少种不同的子序列选择方式
时间: 2024-02-28 21:55:49 浏览: 24
我们可以使用动态规划来解决这个问题。设 $f_i$ 表示以第 $i$ 个字符结尾的、不包含连续的"61"子串的最长子序列的个数。那么,对于第 $i+1$ 个字符,我们可以有两种选择:
1. 将第 $i+1$ 个字符加入到已有的子序列中。这样,对于任意 $j<i$,如果 $f_j>0$,那么我们可以将以第 $j$ 个字符结尾的子序列延长到第 $i+1$ 个字符,从而得到一个以第 $i+1$ 个字符结尾的、不包含连续的"61"子串的最长子序列。因此,我们可以得到转移方程:
$$
f_{i+1} = \sum_{j=1}^i [f_j > 0] \qquad (s_i \neq '6' \text{ or } s_j \neq '1')
$$
其中 $[x]$ 表示当 $x$ 成立时为 $1$,否则为 $0$。
2. 将第 $i+1$ 个字符作为一个新的子序列的起点。这样,我们只需要考虑前两个字符是否为 "61",即可得到转移方程:
$$
f_{i+1} = 1 + [s_i \neq '6' \text{ or } s_{i+1} \neq '1']
$$
最终的答案即为 $\sum_{i=1}^n f_i$,其中 $n$ 表示字符串的长度。
时间复杂度为 $O(n^2)$,空间复杂度为 $O(n)$。代码如下:
```python
s = input()
n = len(s)
f = [0] * (n + 1)
for i in range(n):
if s[i:i+2] == '61':
f[i+1] = 1
else:
f[i+1] = 1 + [s[i] != '6' or s[i+1] != '1']
for j in range(1, i):
if f[j] > 0 and (s[i] != '6' or s[j] != '1'):
f[i+1] += f[j]
ans = sum(f[1:])
print(ans)
```