lightoj1033

CODE

#include <iostream>
#include <cstring>

using namespace std;
char s[105];
int len,ncase;
int dp[105][105];
int main()
{
        int t ;
        cin >> t;
        while(t--)
        {
                memset(dp,0,sizeof(dp));
                cin >> s;
                int len=strlen(s);
                for(int l=1;l<=len;l++)
                        for(int i=0;i<len;i++)
                {
                        int j=i+l-1;
                        if(j>=len)continue;
                        if(s[i]==s[j])dp[i][j]=dp[i+1][j-1];
                        else
                                dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
                }
                cout <<"Case "<<++ncase<<": "<<dp[0][len-1]<<endl;
        }
        return 0;
}