本文主要是介绍NYOJ 749 Splits the string，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
OJ题目 ： http://acm.nyist.net/JudgeOnline/problem.php?pid=749
描述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
#define inf 100000000
bool judge(string s)
{int len = s.length();int i , j;for(i = 0,j = len;i <= j;i++,j--){if(s[i] != s[j]) return false;}return true;
}int main()
{int n;int x[202];bool f[1002][1002];int dp[1002];string s;while(cin >> s){memset(dp , 0 , sizeof(dp));int len = s.length();for(int i = 0;i < len;i++){dp[i] = i + 1;for(int j = 0;j <= i;j++){if(s[i] == s[j] && judge(s.substr(j , i - j + 1)))dp[i] = Min(dp[i] , dp[j - 1] + 1);}}cout << dp[len - 1] << endl;}return 0;
}
这篇关于NYOJ 749 Splits the string的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
