51nod 1154 dp

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1154

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示例

3
原本以为N^2会爆炸后来发现好像也不会= =倒是题意搞懵逼我了，题意是必须全部划分为回文子串，求最少划分几个，我以为可以出现非回文子串,就是0......天真
dp[i]表示前i个字符的答案，第i个字符可能单独也可能与前面的某一串相连构成一个回文串，答案就是 dp[i]=MIN{dp[j]+1 | j<i&&j+1--i构成回文串}

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define inf 0x3f3f3f3f

 LL mod=1e9+;

 int dp[];

 char s[];

 bool ok(int a,int b)

 {

     int m=b-((b-a)>>);

     for(int i=a,j=b;i<=m;++i,--j)

         if(s[i]!=s[j]) return ;

     return ;

 }

 int main()

 {

     int N,i,j;

     scanf("%s",s+);

     N=strlen(s+);

     for(i=;i<=N;++i)

     {

         dp[i]=dp[i-]+;

         for(j=;j<i;++j)

         {

             if(ok(j+,i)&&dp[i]>dp[j]+) dp[i]=dp[j]+;

         }

     }

     printf("%d\n",dp[N]);

     return ;

 }