题解 UVA11584 【Partitioning by Palindromes】

星沐 · 2018-09-26 19:10:53 · 题解

这是一道经典的区间DP。

当然深搜也能过

看题之后写了个判断是否为回文串的函数，虽然最后并没有用上， 但还是码上吧, 很简单的函数

/*int judge(string s)
{
     int i,ls;
     int flag=1;
     ls=s.length();
     for(i=0;i<ls/2;i++)
     {
         if(s[i]!=s[ls-1-i])
         {
             flag=0;
             break;
         }
     }
     return flag;
}*///判断回文串的函数。

状态转移方程c[i]=min(c[i],c[j-1]+1);

然后记得边界条件要写对，读题很重要；

正解如下

如有不到位的地方，欢迎指正，谢谢

bool tt[i][j]指i位置元素到j位置元素是否为回文串。相当于标记，优化了判断字符串的速度。

#include<bits/stdc++.h>
using namespace std ;
string s;
int t;
int c[1005];    
bool tt[1005][1005];
int work(string s)
{
    int ls=s.length();
    for(int i=0;i<ls;++i)
    {
        c[i]=i+1;//初始条件
        for(int j=i;j>=0;j--)
        {
            if (i==j||s[j]==s[i]&&(j+1==i||tt[j+1][i-1])) //注意奇数和偶数长度的字符串。 
            {
                tt[j][i]=1;//注意j到i才是正序； 
                if (j==0) 
                 {
                    c[i]=1; //当j==0时，题目是问子串的个数，不是分割次数！！！
                 } 
                else
                {
                    c[i]=min(c[i],c[j-1]+1);//状态转移方程； 
                }
            }   
         }
    }
    return c[ls-1];//因为字符串下标是从0开始的
}
int main()
{
    cin>>t;
    for(int i=1;i<=t;++i)
    {
        cin>>s;
        memset(c,0x3f,sizeof(c));//记得初始化
        memset(tt,0,sizeof(tt));
        cout<<work(s)<<endl;//换行一定要打。
    }
    return 0；
}