Uva 11584，划分成回文串

题目链接：https://uva.onlinejudge.org/external/115/11584.pdf

题意：

一个字符串，将它划分一下，使得每个串都是回文串，求最少的回文串个数。

分析：

d(i)到第 i 个字符时的最优解（即最少划分为几个回文串），就有方程 d(i) = min(d(j)) + 1;(其中s[j+1,i]要是回文串)。

这样一来，枚举就是O(n^2)的复杂度，如果按照普通的判断s[j+1,i]是否是回文串，时间复杂度为O(n^3);先用O(n^2)的复杂度预处理is_huiwen[i][j]判断是否是回文串。前面我采用的DP的方案。这里学了一个更好写的方案，——中心扩展法。

这里值得注意的是：预留一个dp[0] = 0;这样在当前面没有回文串时，而整个字符串是回文串的时候，就有d[i] = d[0]+1 =1;

#include <bits/stdc++.h>

using namespace std;

const int maxn = +;

int n,kase,p[maxn][maxn],d[maxn];

bool vis[maxn][maxn];

char s[maxn];

int is_palindrome(int i, int j)

{

    if(i >= j) return ;

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

    if(vis[i][j] == true) return p[i][j];

    vis[i][j] = true;

    p[i][j] = is_palindrome(i+, j-);

    return p[i][j];

}

int main()

{

    int T;

    scanf("%d",&T);

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

    {

        memset(vis,,sizeof(vis));

        scanf("%s",s+);

        n = strlen(s+);

        d[] = ;

        is_palindrome(,n);

        for(int i=; i<=n; i++)

        {

            d[i] = i+;

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

            {

                if(is_palindrome(j+,i))

                    d[i] = min(d[i],d[j]+);

            }

        }

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

    }

    return ;

}

巴特西

Uva 11584，划分成回文串

最新文章

热门文章