题目大意：给出一个字符串，将它划分成尽量少的子串，使得每个子串都是回文串。
首先预处理出每个子串是否是回文串，，b[i][j]=1表示子串a[i…j]是回文串，b[i][j]=0表示子串a[i…j]不是回文串。
用d[i]表示前i个字符的最少划分数。枚举最后一个划分是在哪从而完成递推。
状态转移方程：d[i]=min { d[u]+1 }（b[u+1][i]==1）
#include<stdio.h>#include<stdlib.h>#include<string.h>char a[1100];int b[1010][1010];int d[1010];int main(void){int i,j,n,pi,qi,minp;scanf("%d",&pi);getchar();for(qi=0;qi<pi;qi++){gets(a+1);n=strlen(a+1);for(j=1;j<n;j++){b[j][j]=1;if(a[j]==a[j+1]){b[j][j+1]=1;}else{b[j][j+1]=0;}}b[n][n]=1;for(i=2;i<n;i++){for(j=1;j<=n-i;j++){if((a[j]==a[j+i])&&(b[j+1][j+i-1]==1)){b[j][j+i]=1;}else{b[j][j+i]=0;}}}d[1]=1;for(i=2;i<=n;i++){if(b[1][i]==1){d[i]=1;}else{minp=d[i-1]+1;for(j=2;j<i;j++){if((b[i-j+1][i]==1)&&(d[i-j]+1<minp)){minp=d[i-j]+1;}}d[i]=minp;}}printf("%d\n",d[n]);}return 0;}
一定要成为你工作最大的资产。
