题目链接
的预处理i~j是不是回文串然后 的DP11584 Partitioning by Palindromes
Can you read upside-down? We say a sequence of characters is a palindrome if it is the same written forwards and backwards. For example, ‘racecar’ is a palindrome, but ‘fastcar’ 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
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.
Output
For each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes.Universidad de Valladolid OJ: 11584 – Partitioning by Palindromes 2/2
Sample Input
3 racecar fastcar aaadbccb
Sample Output
1 7 3
/* ***********************************************Author:CKbossCreated Time :2015年02月09日 星期一 12时32分31秒File Name:UVA11584.cpp************************************************ */;const int maxn=1111;int n;bool isP[maxn][maxn];char str[maxn];int dp[maxn];void init(){for(int i=0;i<n;i++){for(int j=0;j<n;j++){int left=i-j,right=i+j;if(left>=0&&right<n){if(str[left]==str[right])isP[left+1][right+1]=true;else break;}else break;}}for(int i=0;i<n-1;i++){int left=i,right=i+1;if(str[left]==str[right]){for(int j=0;j<n;j++){left=i-j;right=i+1+j;if(left>=0&&right<n) ;else break;if(str[left]==str[right])isP[left+1][right+1]=true;else break;}}}}int main(){T_T;scanf(“%d”,&T_T);while(T_T–){scanf(“%s”,str);n=strlen(str);memset(dp,63,sizeof(dp));memset(isP,0,sizeof(isP));init();dp[0]=0;for(int i=1;i<=n;i++){for(int j=0;j<i;j++){if(isP[j+1][i])dp[i]=min(dp[i],dp[j]+isP[j+1][i]);}}printf(“%d\n”,dp[n]);}return 0;}
，不然你大概会一直好奇和不甘吧——家门前的那条小路，
