UVA11584划分成回文串 Partitioning by Palindromes

划分成回文串 Partitioning by Palindromes

题面翻译

回文子串(palind)

问题描述：

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

输入格式：

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

输出格式：

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

由 @C919 提供翻译

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

3
racecar
fastcar
aaadbccb

样例输出 #1

1
7
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 <iostream>
#include <cstring>
#include <cstdio>#define N 10000using 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;
}