题目链接
题目大意
给你几个字符串 (1<len(s)<1000) ,要你求每个字符串的回文序列个数.对于10008取模.
Solution
区间DP。
比较典型的例题。
状态定义:
令 \(f[i][j]\) 表示 \(i\) 到 \(j\) 的回文序列个数，\(s\) 为给出的字符串.
状态转移:
- \(s[i]\neq s[j]\)
那么此时 \(f[i][j]\) 即为\(f[i][j-1]\),\(f[i+1][j]\)之和.
但由于 \(i+1->j-1\)的我们明显重复统计了,所以方程即为:
\]
2. $s[i]=s[j]$
此时考虑,对于 $i+1$ 到 $j-1$ 每一个回文序列,我们都可以把 $s[i]$和$s[j]$ 加在两边.同时还多了 $s[i],s[j]$ 这个序列.
所以此时方程即为:
$$f[i][j]=f[i+1][j]+f[i][j-1]+1$$
### Code
```cpp
#include
using namespace std;
const int maxn=1008;
const int mod=10007;
int f[maxn][maxn];
int n,t;
char s[maxn];
int main()
{
cin>>t;
for(int k=1;k<=t;k++)
{
scanf("%s",s);
n=strlen(s);
memset(f,0,sizeof(f));
for(int i=0;i<n;i++)
{
f[i][i]=1;
if(i<n-1)
if(s[i]s[i+1])
f[i][i+1]=3;
else f[i][i+1]=2;
}
for(int len=3;len<=n;len++)
for(int l=0;l<=n-len;l++)
{
int r=l+len-1;
if(s[l]s[r])
f[l][r]=(f[l][r-1]+f[l+1][r]+1)%mod;
else
f[l][r]=(f[l][r-1]+f[l+1][r]-f[l+1][r-1]+mod)%mod;
}
printf("Case %d: %d\n",k,f[0][n-1]);
}
}