题解：SP15558 IITKWPCE - Let us play with strings

原题Link

这题只有橙我吃 Manacher 至少蓝吧。

题意

给定字符串 $s$，要把 $s$ 划分成数量最小的回文串，求这个数量。

Solution

这一种划分类问题，通常是 DP。

定义 $dp_i$ 表示前 $i$ 个字符的最小划分。 边界就是前 $0$ 个字符的最小划分是 $0$。注意到要求最小，所以 $dp$ 数组要初始化成极大值。 答案显然是 $dp_n$。 推转移，发现当 $i$ 到 $j$ 这一个串是回文串时，$dp_i=\min\{dp_i,dp_j+1\}$。

这个时候发现，哎这个转移怎么这么坏呀，这么要求回文串呀这个转移要求回文串，这么快速的预处理回文串呢？那肯定是 Manacher 啊。 用 Manacher 预处理所以串，然后直接 DP 就行了。