基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
有一个字符串S，求S最少可以被划分为多少个回文串。
例如：abbaabaa，有多种划分方式。
a|bb|aabaa - 3 个回文串
a|bb|a|aba|a - 5 个回文串
a|b|b|a|a|b|a|a - 8 个回文串
其中第1种划分方式的划分数量最少。
Input
输入字符串S(S的长度<= 5000)。
Output
输出最少的划分数量。
Input示例
abbaabaa
Output示例
3
相关问题
最长回文子串 V2（Manacher算法） 最长回文子串 回文串划分 V2 6
40
回文字符串 10
//显然dp，dp[i] 表前 i 个数最少能变几个回文
dp[i] = min(dp[i], dp[z-1]+1) "s[z],s[z+1]...s[i]" 是一个回文串
用马拉车就是 n*2n ,5000*10000，话说弱鸡我debug一万年。。。
不用就是 n^3 吧，不大懂
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MOD 1000000007
#define MX 5005 int n;
int len;
char temp[MX];
char str[MX*];
int p[MX*];
int dp[MX*]; void Init()
{
len = ;
str[len++]='@';
str[len++]='#';
n = strlen(temp);
for (int i=;i<n;i++)
{
str[len++]=temp[i];
str[len++]='#';
}
memset(p,,sizeof(p));
} void Manacher()
{
Init();
int mx = , id =;
for (int i=;i<len;i++)
{
p[i] = mx>i ? min(p[*id-i],mx-i):;
while (str[i+p[i]]==str[i-p[i]]) p[i]++;
if (i+p[i]>mx)
{
mx = i+p[i];
id = i;
}
}
} int main()
{
while (scanf("%s",temp)!=EOF)
{
Manacher(); for (int i=;i<n;i++)
{
dp[i] = i+; //初值
int pos = (i+)*;
for (int j=pos;j>=;j--)
{
if(j+p[j]->=pos)
{
int pre = (j-(pos-j))/-;
if (pre==) dp[i]=;
else dp[i]= min(dp[pre-]+,dp[i]);
}
}
}
printf("%d\n",dp[n-]);
}
return ;
}