题意：求一串字符中回文子序列的个数。
1001
注意到任意一个回文子序列收尾两个字符一定是相同的，于是可以区间dp，用dp[i][j]表示原字符串中[i,j]位置中出现的回文子序列的个数，有递推关系：
dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]
如果i和j位置出现的字符相同，那么dp[i][j]可以由dp[i+1][j-1]中的子序列加上这两个字符构成回文子序列，也就是
dp[i][j]+=dp[i+1][j-1]，注意边界特判一下就可以了
以上一段是官方解题报告原话，哎~多校时居然想的不知道到哪去了。。。。。当然，有这些还不够，还要自己推一下a[i]==a[j]时，不仅要dp[i][j]+=dp[i+1][j-1]，还要dp[i][j]+=1。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[1005][1005];
int main()
{
int num=1;
char a[1005];
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",&a);
int l=strlen(a);
memset(f,0,sizeof(f));
for(int i=0;i<l;i++)f[i][i]=1;
for(int j=1;j<l;j++)
{
for(int i=j-1;i>=0;i--)
{
f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1];
if(a[i]==a[j])
{
f[i][j]+=f[i+1][j-1];
f[i][j]++;
}
f[i][j]=f[i][j]%10007;
}
}
cout<<"Case "<<num++<<": ";
cout<<(f[0][l-1]+10007)%10007<<endl;
}
return 0;
}