lightoj1044

CODE

#include <iostream>
#include <cstring>
using namespace std;
int dp[1005];
char s[1005];
int ncase;
int judge[1005][1005];
int main()
{
        int t;
        cin >> t;
        while(t--)
        {
                memset(judge,0,sizeof(judge));
                memset(dp,0x3f,sizeof(dp));
                cin >> s;
                int len=strlen(s);
                for(int i=0;i<len;i++)
                        judge[i][i]=1;
                for(int l=2;l<=len;l++)
                        for(int i=0;i<len;i++)
                {
                        int j=i+l-1;
                        if(j>=len)break;
                        if(s[i]==s[j])
                        {
                                if(l==2)judge[i][j]=1;
                                else    judge[i][j]=judge[i+1][j-1];
                        }
                }
                for(int i=0;i<len;i++)
                {
                        for(int j=0;j<=i;j++)
                        {
                                if(judge[j][i])
                                {
                                        if(!j)dp[i]=1;
                                        else dp[i]=min(dp[i],dp[j-1]+1);
                                }
                        }
                }
                cout <<"Case "<<++ncase<<": ";
                cout << dp[len-1]<<endl;
        }
        return 0;
}