UVA 11584 Partitioning by Palindromes .

题目地址：http://vjudge.net/problem/UVA-11584

d[i]表示字符0~i划分成最小回文串的个数

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b)  for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int maxn=1000+5;
int c[maxn][maxn];
int d[maxn];
char s[maxn];
int Check(int i,int j){if(c[i][j]!=-1) return c[i][j];REP(k,0,maxn) {if(s[i+k]!=s[j-k]) return c[i][j]=0;if(i+k>=j-k) break;}return c[i][j]=1;
}
int main(int argc, char const *argv[])
{int T; scanf("%d",&T);while(T--){scanf("%s",s);int len=strlen(s);memset(c,-1,sizeof(c));d[0]=1;REP(i,1,len-1) {d[i]=d[i-1]+1;REP(j,0,i-1) if(Check(j,i)) d[i]=min(d[i],d[j-1]+1);}printf("%d\n", d[len-1]);}return 0;
}