51nod 1154 回文串划分 2019/03/25

1154 回文串划分

1. 1 秒
2.  
3. 131,072 KB
4.  
5. 40 分
6.  
7. 4 级题

有一个字符串S，求S最少可以被划分为多少个回文串。

例如：abbaabaa，有多种划分方式。

a|bb|aabaa - 3 个回文串

a|bb|a|aba|a - 5 个回文串

a|b|b|a|a|b|a|a - 8 个回文串

其中第1种划分方式的划分数量最少。

 收起

输入

输入字符串S(S的长度<= 5000)。

输出

输出最少的划分数量。

输入样例

abbaabaa

输出样例

3

manacher处理出l到r是否是回文串，然后dp，

f[i]代表前i个最少可以划分的回文串数目