龙哥能在健忘症的影响下讲完S6第一个王者的故事吗?
众所周知,龙哥在S6赛季登上了国服的第一个王者。
龙哥的游戏历程可以用一个仅包含'o','x','?'
的胜败序列表示,其中'o'
为胜场,而'x'
为败场。由于龙哥有健忘症而且现在已经是S14赛季了,还有一些场次龙哥已经不记得输赢了,因此用'?'
表示该场次可能是'o'
或'x'
。
在这个游戏中,存在一种影响玩家上分隐藏机制,每个败场将基于该赛季之前所有的胜场进行补分(减少隐藏分的术语),而每个胜场将基于该赛季之前所有的败场补分。形式化说,对于某个胜负序列,每个'ox'
子序列将补分,每个'xo'
子序列将补分。
龙哥虽然已经记不清那些由'?'
表示的场次的结果了,但是知道自己当时补的分是所有可能的胜败序列中最少的。龙哥想考考你他当时最少补多少分。
子序列的定义:给定一个序列,另一个序列,若存在一个严格递增的的下标序列对所有的,都满足,则称是的子序列。