小红拿到了一个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链游项目方科学家脚本开发培训

从业7年-专注一级市场


微信:btc9767
TELEGRAM :https://t.me/btcok9

具体资料介绍

web3的一级市场千万收益的逻辑


进群点我



qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 小红拿到了一个01串。所谓01串,指仅由’0’和’1’两种字符组成的字符串。 小红可以进行任意次以下操作: 选择字符串的一个字符,将其取反(’0’变’1’或者’1’变’0’)。 小红定义一个01串为好串,当且仅当该01串不包含”010″子串和”101″子串。 例如,”1001″是好串,但”100100″则不是好串。 小红想知道,自己最少操作多少次可以将给定字符串变成好串?