重庆百度整站优化,如何创建一个平台,成都互联网制作,如何制作个人网页?划分成回文串 Partitioning by Palindromes
题面翻译
回文子串(palind)
问题描述#xff1a;
当一个字符串正序和反序是完全相同时#xff0c;我们称之为“回文串”。例如“racecar”就是一个回文串#xff0c;而“fastcar”就不是。现在给一个字符串s#xff0c;把它分…划分成回文串 Partitioning by Palindromes
题面翻译
回文子串(palind)
问题描述
当一个字符串正序和反序是完全相同时我们称之为“回文串”。例如“racecar”就是一个回文串而“fastcar”就不是。现在给一个字符串s把它分割成若干个互不相交的回文子串求分割的回文子串的最少个数。
输入格式
第一行为正整数t(≤10)表示数据组数接下来t行每行一个完全由小写字母组成的字符串长度不超过1000。
输出格式
对于每组数据输出最少回文子串数。
由 C919 提供翻译
题目描述
PDF 输入格式 输出格式 样例 #1
样例输入 #1
3
racecar
fastcar
aaadbccb样例输出 #1
1
7
3solution
采用动态规划的思想
初始状态为dp[i]i1即一个字符串str.substr(0,i1)最多包涵i1一个回文串建立状态转移方程dp[i]min(dp[j]-1,dp[i])其中子串str.substr(j,i-j1)为一个回文串dp[i]表示子串str.substr(0,i1) 最少有回文子串的数目
#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;
}
