第4题     半回文串 查看测评数据信息

给定一个长度为n的只含小写英文字母的字符串S和一个整数k,请你将S分成k个子字符串，使得每个子字符串变成半回文串需要修改的字符数目最少。请你返回一个整数，表示需要修改的最少字符数目。

下面定义什么事半回文串：如果一个字符串从左往右和从右往左读是一样的，那么它是一个回文串。如果长度为len的字符串存在一个满足1<=d<len的正整数d,1en%d=0成立且所有对d做除法余数相同的下标对应的字符连起来得到的字符串都是回文串，那么我们说这个字符串是半回文串。比方说"aa"，"aba","adbgad"和"abab"都是半回文串，而”a”，"ab"和"abca"不是。子字符串指的是一个字符串中一段连续的字符序列。

输入格式

第一行一个长度是n的字符串S

第二行一个整数k

2<=n<=200,1<=k<=n/2

输出格式

一个整数

输入/输出例子1

输入：

abcac

2

输出：

1

样例解释

 我们可以将S分成子字符串"ab"和"cac"。子字符串"cac"已经是半回文串。如果我们将"ab"变成"aa",它也会变成个d=1的半回文串。该方案是将S分成2个子字符串的前提下，得到2个半回文子字符串需要的最少修改次数。所以答案为1。

dp套dp是什么

做题目先搞第一个dp，但是光凭第一个dp可能搞不完，中间再用第二个dp预处理一些值，再继续第一个dp继续做。

第二个dp可能是线性的等等的。

又或者说是先预处理一个dp，然后再进行第二个dp。

反正不是真正意义上的dp“套”dp

这题咋做

做法1

f(i, j) 表示枚举到第i位，j表示枚举的这个字符串的头部在哪，头是j，尾是i，也就是字符串中的j~i

对于每个字符串，枚举约数，变成很多段，每一段用贪心求出变成回文串次数，总次数就出来了，然后取一个总最小次数，也就是整个字符串最小次数

这里跟做法2差不多，没做法1的代码和详解，我们直接看做法2

做法2
直接把一串字符串变成k个半回文很难搞，用大局观。

f(i, j): 当前考虑到第i个字符，恰好划分成j段
转移：
枚举k，才知道第j段从哪开始

f(i, j)=f(k-1, j-1)+(k~i)这一段变成半回文的花费

O(n^3)

预处理 k~i 变成半回文的花费
g(i, j)，i到j这一段字符变成半回文需要花费