lightoj1025

CODE

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