1154 回文串划分(DP+Manacher)

1154 回文串划分

基准时间限制：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示例

相关问题

最长回文子串 V2（Manacher算法）最长回文子串回文串划分 V2 6

回文字符串 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 ;

 }

巴特西

1154 回文串划分(DP+Manacher)

最新文章

热门文章