description

 
给定字符串，求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。

例如字符串aba中，回文子序列为 a aba b a aa
，共5个。内容相同位置不同的子序列算不同的子序列。

input

 
第一行一个整数T，表示数据组数。之后是T组数据，每组数据为一行字符串。

output

 
对于每组数据输出一行，格式为"Case #X: Y"，X代表数据编号（从1开始），Y为答案。答案对100007取模。

sample_input

 
5
aba
abcbaddabcba
12111112351121
ccccccc
fdadfa

sample_output

 
Case #1: 5
Case #2: 277
Case #3: 1333
Case #4: 127
Case #5: 17

刚刚看自己5月份时候自己的代码，看半天才懂，脊梁骨开始发冷，顿时没有了看《斗罗大陆》的心情了T^T

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char m[999];
int t;
int dp[999][999];
int main()
{
    //freopen("data.in.txt","r",stdin);
    while(~scanf("%d",&t))
    {
         int cnt=1;
         while(t--)
         {memset(dp,0,sizeof(dp));


         scanf("%s",m);
         int n=strlen(m);
         for(int i=0;i<n;i++)
         {
              for(int j=i;j>=0;j--)
              {
                   if(m[i]==m[j])
                   {
                        dp[j][i]=(dp[j+1][i]+dp[j][i-1]+1)%100007;
                   }
                   else
                   {
                        dp[j][i]=dp[j+1][i]+dp[j][i-1]-dp[j+1][i-1];//其实蛮好懂的啊
                        dp[j][i]+=100007;
                        dp[j][i]=dp[j][i]%100007;
                   }
              }
         }
         printf("Case #%d: ",cnt++);
         printf("%d\n",dp[0][n-1]);}
    }
    return 0;
}