WolfDelaymasterHard
作者:袁宇韬
关键词:动态规划
题目简述
给定一个由wo?
三种字符组成的字符串,问有多少种方案将?
变为w
或o
,使得新字符串为若干个长度为偶数且前一半全部为w
,后一半全部为o
的字符串连接形成。答案对取模。
算法一
将最终字符串中的每一段字符串的前一半称为w
部分,后一半称为o
部分。
用表示前个字符的答案。则容易通过枚举最后一段的长度得到一个的DP。考虑对这个DP的优化。
考虑能够转移到的条件。令。分两种情况考虑。
如果w
部分中只有?
,则对于一个固定的,w
部分可行的条件为s[j..j+l-1]
全部为?
,o
部分可行的条件为s[j..j+2*l-1]
中没有w
。满足条件的l
为一个区间,可以用前缀和转移。
如果w
部分中有至少一个w
,则对于一个固定的,w
部分可行的条件为s[i-2*l..i-l-1]
中没有o
且有至少一个w
,o
部分可行的条件为s[i-l..i-1]
中没有w
。由于o
部分中没有w
,则w
部分中一定包含s[i]
之前的最近一个w
字符,而o
部分中则包含这个w
字符之后的所有o
字符。满足条件的l
为一个区间,可以用前缀和转移。
时间复杂度。