Palindrome Partitioning LightOJ - 1044（回文串最小分割数，O(n^2)预处理子串是否回文）

2024-03-22 17:08:34

题意：将一个字符串分割成最少的字符串，使得分割出的每个字符串都是回文串。输出最小的分割数。

方法（自己的）：先O(n^2)（用某个点或某个空区间开始，每次向左右扩展各一个的方法）处理出所有子串是否回文。然后常规区间dp,ans[i][j]表示i到j的子串的最小划分数。如果i到j的子串本身为回文串，那么ans[i][j]为1，否则枚举所有方案将i到j划分为两个区间，取所有两个区间结果之和的最小值。

方法（其他，大概就是压了一下空间，压了一下时间的常数）：http://blog.csdn.net/l123012013048/article/details/49475845

解题思路：用dp[i]表示前i个字符划分成回文串，需要划分成多少个部分
接着枚举j，如果[i,j]回文，那么dp[i] = min(dp[i], dp[j - 1] + 1)

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 bool ok[][];

 char s[];

 int T,TT,len,ans[][];

 int get(int l,int r)

 {

     if(ans[l][r])    return ans[l][r];

     if(l==r)    return ;

     if(ok[l][r])    return ans[l][r]=;

     int anss=0x3f3f3f3f,i;

     for(i=l;i<r;i++)

         if(ok[l][i])

             anss=min(anss,get(i+,r)+);

     return ans[l][r]=anss;

 }

 int main()

 {

     int i,l,r;

     bool now;

     scanf("%d",&T);

     for(TT=;TT<=T;TT++)

     {

         scanf("%s",s+);

         len=strlen(s+);

         memset(ans,,sizeof(ans));

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

             for(l=i,r=i,now=;l>=&&r<=len;l--,r++)

             {

                 if(s[l]!=s[r])    now=;

                 ok[l][r]=now;

             }

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

             for(l=i,r=i+,now=;l>=&&r<=len;l--,r++)

             {

                 if(s[l]!=s[r])    now=;

                 ok[l][r]=now;

             }

         printf("Case %d: %d\n",TT,get(,len));

     }

     return ;

 }

码农公寓