遇到一个字符串的问题，求解答。
Tom 又碰到了一道字符串的题目。有一个字符串 s(1<=|s|<=3e5，|s| 为奇数 )，这个字符串只包含 0,1 和字符 '.'，这个 '.' 字符可以任意变为 0 或者 1。现在可以通过一些操作来缩短这个字符串，每次操作可以任意选择连续的三个字符，然后将这个连续的三个字符变成出现数量最多的那个字符 ( 比如001变为0，101变为1，1.0可以变为0 也可以变为 1)。通过更改字符 '.'，问通过 (|s|-1)/2次操作后最终这个字符串只剩下一个 1 的方案有多少种，答案对1e9+7取模。输入一行字符串 s输出一个数表示方案数。
展开
收起
1
条回答
写回答
写回答
-
操作次数为
，1.0.1 长度为 5 就是可以操作 2 次。分别可以把字符串变为 10001 10011 11001 11011，这四种都可以使得最后只剩下 1，所以答案为 4 种。 因为最后是剩下 1 所以我们肯定优先消去 0，dp i,j,k 的含义就是前 i 个字符中把第 j 个字符变成 k 的方案数。把所有数据处理一遍再求一遍最大值即可。
因此：输入："1.0.1" 输出：4
2021-12-23 18:36:09赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
