Splits the string

時間限制：1000 ms ?|? 內存限制：65535 KB 難度：3 描述

Hrdv is interested in a string,especially the palindrome string.So he wants some palindrome string.
A sequence of characters is a palindrome if it is the same written forwards and backwards. For example, 'abeba' is a palindrome, but 'abcd' is not.
A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence. For example, ('race', 'car') is a partition of 'racecar' into two groups.
Given a sequence of characters, we can always create a partition of these characters such that each group in the partition is a palindrome! Given this observation it is natural to ask: what is the minimum number of groups needed for a given string such that every group is a palindrome?
For example:
'racecar' is already a palindrome, therefore it can be partitioned into one group. 'fastcar' does not contain any non-trivial palindromes, so it must be partitioned as ('f', 'a', 's', 't', 'c', 'a', 'r'). 'aaadbccb' can be partitioned as ('aaa', 'd', 'bccb'). Input begins with the number n of test cases. Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within.

輸入

Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within.

輸出

For each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes.

樣例輸入

racecar fastcar aaadbccb

樣例輸出

1 7 3

上傳者

TC_胡仁東

#include <iostream> #include <cstring> #include <cstdio> using namespace std; int dp[1005]; char a[1005];int judge(int i, int j){//?? ?while(a[i] == a[j]){ //?? ??? ?if(i == j) //?? ??? ??? ?break; //?? ??? ?i++; //?? ??? ?if(i == j) //?? ??? ??? ?break; //?? ??? ?j--; //?? ??? ?if(i == j) //?? ??? ??? ?break; //?? ?} //?? ?if(i == j && a[i] == a[j]) //?? ??? ?return 1; //?? ?else //?? ??? ?return 0;//上面判斷回文太麻煩了int mid = (i + j) >> 1;int m = i;for(int i; i <= mid; i++){if(a[i] != a[j - i + m])? //注意j - i時要加上數組片段傳來的起點. return 0;} return 1; }int main(){while(~scanf("%s", a + 1)){int len = strlen(a + 1);for(int i = 1; i <= len; i++){dp[i] = i;for(int j = 1; j <= i; j++){if(a[i] == a[j] && judge(j, i)){??????? //dp[i]表示的是0到i的最少回文串數 dp[i] = min(dp[i], dp[j - 1] + 1);? //j從是從0開始掃描到i如果發現j到i是回文，//則j到i為一個回文串，就可以得到這個遞推關系 }}}?? ?printf("%d\n", dp[len]);??? ?}return 0; }

　　

轉載于:https://www.cnblogs.com/zhumengdexiaobai/p/7429674.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的16-最少回文数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。