uva 11584 - Partitioning by Palindromes 最少回文串划分

末蓝、 2021-12-19 03:09 175阅读 0赞

## 题意： ##

## 给一个字符串， 要求把它分割成若干个子串，使得每个子串都是回文串。问最少可以分割成多少个。 ##

## 方法一：f\[i\]表示以i结尾的串最少可以分割的串数。f\[i\] = min\{ f\[j\]+1, 串\[j,i\]是回文串&&1<=j<=i \} ##

## 方法二：定义dp\[i\]为1到i前i个字符至少被划分成回文串的个数。状态转移方程为： ##

## dp(i) = min\{dp(j - 1) + 1\} 1 <= j <= i ,如果(j,i)之间的字符是回文字符串。O（n^2）预处理s\[i..j\]是否为回文串，枚举每个中心，不断向左右延伸标记，直到延伸到的左右字符不同为止。也可以用记忆化搜索（参考自刘汝佳）。 ##

## 代码： ##

// UVa11584 Partitioning by Palindromes
    // Rujia Liu
    // This code is slightly different from the book.
    // It uses memoization to judge whether s[i..j] is a palindrome.
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    const int maxn = 1000 + 5;
    int n, kase, vis[maxn][maxn], p[maxn][maxn], d[maxn];
    char s[maxn];
    
    ///记忆化搜索
    int is_palindrome(int i, int j)
    {
        if(i >= j) return 1;
        if(s[i] != s[j]) return 0;
        if(vis[i][j] == kase) return p[i][j];
        vis[i][j] = kase;
        p[i][j] = is_palindrome(i+1, j-1);
        return p[i][j];
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        memset(vis, 0, sizeof(vis));
        for(kase = 1; kase <= T; kase++)
        {
            scanf("%s", s+1);
            n = strlen(s+1);
            d[0] = 0;
            for(int i = 1; i <= n; i++)
            {
                d[i] = i+1;///每个字母作为一个回文串
                for(int j = 0; j < i; j++)
                    if(is_palindrome(j+1, i)) d[i] = min(d[i], d[j] + 1);
            }
            printf("%d\n", d[n]);
        }
        return 0;
    }