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