小红拿到了一个01串。所谓01串，指仅由’0’和’1’两种字符组成的字符串。小红可以进行任意次以下操作：选择字符串的一个字符，将其取反（’0’变’1’或者’1’变’0’）。小红定义一个01串为好串，当且仅当该01串不包含”010″子串和”101″子串。例如，”1001″是好串，但”100100″则不是好串。小红想知道，自己最少操作多少次可以将给定字符串变成好串？

区块链毕设网qklbishe.com为您提供问题的解答

小红拿到了一个01串。所谓01串，指仅由’0’和’1’两种字符组成的字符串。
小红可以进行任意次以下操作：

选择字符串的一个字符，将其取反（’0’变’1’或者’1’变’0’）。

小红定义一个01串为好串，当且仅当该01串不包含”010″子串和”101″子串。
例如，”1001″是好串，但”100100″则不是好串。
小红想知道，自己最少操作多少次可以将给定字符串变成好串？

s = input().strip()
n = len(s)

if n < 3:
print(0)
else:
# 初始化动态规划的前两个字符状态
prev_dp = {
(‘0’, ‘0’): (s[0] != ‘0’) + (s[1] != ‘0’),
(‘0’, ‘1’): (s[0] != ‘0’) + (s[1] != ‘1’),
(‘1’, ‘0’): (s[0] != ‘1’) + (s[1] != ‘0’),
(‘1’, ‘1’): (s[0] != ‘1’) + (s[1] != ‘1’),
}

# 允许的第三个字符的映射
allowed_c_map = {
(‘0’, ‘0’): [‘0’, ‘1’],
(‘0’, ‘1’): [‘1’],
(‘1’, ‘0’): [‘0’],
(‘1’, ‘1’): [‘0’, ‘1’],
}

for i in range(2, n):
current_dp = {}
current_char = s[i]
for (a, b), cost in prev_dp.items():
allowed_c = allowed_c_map.get((a, b), [])
for c in allowed_c:
delta = 1 if c != current_char else 0
new_state = (b, c)
new_cost = cost + delta
# 更新当前状态的最小成本
if new_state in current_dp:
if new_cost < current_dp[new_state]:
current_dp[new_state] = new_cost
else:
current_dp[new_state] = new_cost
prev_dp = current_dp

# 取所有可能状态的最小值
print(min(prev_dp.values()))

44:45

以上就是关于问题小红拿到了一个01串。所谓01串，指仅由’0’和’1’两种字符组成的字符串。
小红可以进行任意次以下操作：
选择字符串的一个字符，将其取反（’0’变’1’或者’1’变’0’）。小红定义一个01串为好串，当且仅当该01串不包含”010″子串和”101″子串。
例如，”1001″是好串，但”100100″则不是好串。
小红想知道，自己最少操作多少次可以将给定字符串变成好串？的答案

欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程

区块链NFT链游项目方科学家脚本开发培训