#P17985. Strategic Stones
Strategic Stones
Strategic Stones
题目描述
给定一个只包含 0、1、? 的字符串。两名玩家轮流操作,先手先行动,直到所有问号被替换:
- 先手每次选择一个问号,将其替换为
0; - 后手每次选择一个问号,将其替换为
1。
已确定的字符不能再改变。游戏结束时,得分为字符串中最长连续 0 段的长度;没有 0 时得分为 。
先手希望得分尽可能大,后手希望得分尽可能小。双方均采用最优策略,求最终得分。
输入格式
第一行一个整数 。接下来 行,每行一个字符串 ,其长度记为 。
输出格式
每个用例输出一行一个整数,表示最终得分。
数据范围
,,所有用例的 之和不超过 。
样例
6
??
000
111
0??0??0
0?0?0?0
00?00?100?0
1
3
0
3
5
5