Lightoj 1044 - Palindrome Partitioning

http://lightoj.com/volume_showproblem.php?problem=1044

1. #include <bits/stdc++.h>
2. using namespace std;
3. bool pal[1001][1001];
4. int main()
5. {
6.     int test, cs  = 1;
7.     scanf("%d", &test);
8.     while( test-- ){
9.             int l;
10.     string s;
11.     cin>>s;
12.     l = s.length();
13.     for(int i = 0; i <l; i++){
14.         pal[i][i] = true;
15.     }
16.     for(int len = 2; len<= l ; len++){
17.         for(int i = 0; i <l-len+1; i++){
18.             int j = i+len-1;
19.             if(len == 2){
20.                 pal[i][j] = (s[i] == s[j]);
21.             }
22.             else{
23.                 pal[i][j] = pal[i+1][j-1] && (s[i] == s[j]);
24.             }
25.             }
26.         }
27.     int c[l];
28.     for (int i=0; i<l; i++)
29.     {
30.         if (pal[0][i] == true)
31.             c[i] = 0;
32.         else
33.         {
34.             c[i] = INT_MAX;
35.             for(int j=0;j<i;j++)
36.             {
37.                 if(pal[j+1][i] == true && 1+c[j]<c[i])
38.                     c[i]=1+c[j];
39.             }
40.         }
41.     }
42.         printf("Case %d: %d\n", cs++, c[l-1] + 1);
43.     }
44.     return 0;
45. }
46.