http://www.lightoj.com/volume_showproblem.php?problem=1044
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define N 1005 6 struct op{ 7 int a,b,len; 8 }mes[N*N]; 9 int dp[N],ct,n; 10 char s[N]; 11 bool map[N][N]; 12 void init() 13 { 14 memset(map,0,sizeof(map)); 15 n=strlen(s+1); 16 for(int i=1;i<=n;i++){ 17 map[i][i]=1; 18 mes[++ct].a=i; 19 mes[ct].b=i; 20 mes[ct].len=1; 21 } 22 if(n>1){ 23 for(int i=1;i<n;i++) 24 if(s[i]==s[i+1]){ 25 map[i][i+1]=1; 26 mes[++ct].a=i; 27 mes[ct].b=i+1; 28 mes[ct].len=2; 29 } 30 } 31 for(int len=3;len<=n;len++) 32 for(int i=1;i<=n-len+1;i++) 33 if(s[i]==s[i+len-1]&&map[i+1][i+len-2]){ 34 map[i][i+len-1]=1; 35 mes[++ct].a=i; 36 mes[ct].b=i+len-1; 37 mes[ct].len=len; 38 } 39 } 40 bool cmp(struct op aa,struct op bb) 41 { 42 return aa.b<bb.b; 43 } 44 int main() 45 { 46 int t,cas=1; 47 scanf("%d",&t); 48 while(t--){ 49 ct=0; 50 scanf("%s",s+1); 51 init(); 52 sort(mes+1,mes+ct+1,cmp); 53 memset(dp,0x3f3f3f,sizeof(dp)); 54 dp[0]=0; 55 for(int i=1;i<=ct;i++) 56 dp[mes[i].b]=min(dp[mes[i].b],dp[mes[i].b-mes[i].len]+1); 57 printf("Case %d: %d ",cas++,dp[n]); 58 } 59 return 0; 60 }