UVA11584划分成回文串 Partitioning by Palindromes

划分成回文串 Partitioning by Palindromes

题面翻译

回文子串(palind)

问题描述：

当一个字符串正序和反序是完全相同时，我们称之为“回文串”。例如“racecar”就是一个回文串，而“fastcar”就不是。现在给一个字符串s，把它分割成若干个互不相交的回文子串，求分割的回文子串的最少个数。

输入格式：

第一行为正整数t(≤10)，表示数据组数；接下来t行，每行一个完全由小写字母组成的字符串，长度不超过1000。

输出格式：

对于每组数据，输出最少回文子串数。

由 @C919 提供翻译

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

3
racecar
fastcar
aaadbccb
1
2
3
4

样例输出 #1

1
7
3
1
2
3

solution

采用动态规划的思想

初始状态为dp[i]=i+1，即一个字符串str.substr(0,i+1)最多包涵i+1一个回文串，建立状态转移方程dp[i]=min(dp[j]-1,dp[i])，其中子串str.substr(j,i-j+1)为一个回文串，dp[i]表示子串str.substr(0,i+1) 最少有回文子串的数目

#include 
#include 
#include 

#define N 10000

using namespace std;

bool isPalindrome(string s, int i, int j) {
    while (i < j) {
        if (s[i] != s[j]) {
            return false;
        } else {
            i++;
            j--;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int dp[N] = {0};
        dp[0] = 1;
        string str;
        cin >> str;
        int l = str.length();
        for (int i = 1; i < l; ++i) {
            dp[i] = i + 1;
            for (int j = 0; j <= i; ++j) {
                if (isPalindrome(str, j, i)) {
                    dp[i] = min(dp[j - 1] + 1, dp[i]); // 状态转移方程
                }
            }
        }
        cout << dp[l - 1] << endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42