题目大意： 

给你一个 长度为 N (N <= 300) 的 01字符串,再给一个正整数M.每次操作可以将一个位置取反，或者将一个长度为M的倍数的前缀取反。问最少需要多少次操作，才能使字符串成为一个循环节为M的循环串.

题目思路:(未验证代码正确性)

    发现制约关系: 循环节的长度与其在原串中的个数.尝试分类讨论.

1. 当 m < sqrt(n)时,  循环节长度不超过 sqrt(n) = 17. 所以可以 2^17 枚举循环节的内容.

    已知循环节的内容S. 由于我们需要支持前缀取反的操作.对于原串的每一个循环节,都提供两种决策:

1.将其变成S  ,代价为c0.  2.将其变成S的反串.代价为 c1.

然后.

然后递推dp即可. 最后一个循环节的情况与前面的整体情况.构成 2 * 2 = 4 转移.

2.当 m > sqrt(n) 的时候,循环节的个数 不超过 17 个,所以枚举每一个循环节 取反或不取反.

    已知每个循环节取不取反.我们需要利用取反操作构造一个答案来迎合最优解. 

    问题转化为:给你一个字符串,让你用最少的代价把他变成一个含有长度为M的循环节的字符串.

那么我们可以贪心的统计每一个循环节的同一个位置的 0 的个数 和 1 的个数. 贪心的转变少的即可.

代码:

https://paste.ubuntu.com/p/3CZQvFxcv6/


题目以及思路出处:2014OI 国家集训队题目 - 《根号算法-不只是分块》