p7152专题

【DP】Bovine Genetics G(P7152)

正题 P7152 题目大意 对于一个原串(只有四种字符),先将所有相邻且相同的字符分割开,对分割得到的若干段翻转,得到编辑后的字符串,现在给出编辑后的字符串(有一些位置不确定),问你有多少种符合的原串 解题思路 对于一个编辑后的字符串,考虑对其进行分割,那么分割合法要满足以下两个条件: 每一段中相邻位置不相同(如果相同,那么对于原串肯定会再分割)对于相邻两段a,b,a的首字符要