【题解】Palindrome subsequence (HDU4632) 区间 Dp -boshi

题意：

给定一个长度不超过 1000 的字符串，求它的回文子串串的数量 mod10007。

分析：

我们知道如果求最长回文子串，我们可以做到 O(n²) 求解。如何做到的呢？如果用 s[i] 表示字符串第 i 位的字符，f(i,j) 表示从 i 到 j 的子串中回文子串的最长长度，那么
$$
f(i,j)=max\begin{cases}
f(i+1,j)\\
f(i,j-1) \\
f(i+1,j-1) +1 & \text{(s[i]==s[j])}
\end{cases}
$$
我们发现求最长回文子串是分 s[i]==s[j] 与否进行转移的。
如果是求回文子串数呢？
经过思考，我们会发现，如果 s[i]!=s[j]，i,j 之间的回文子串只有可能出现在 s[i…j-1] 或 s[i+1…j] 这两个区间中。由于这两个区间有重复部分 [i+1…j-1]，所以我们不妨像容斥原理那样将中间的减去。
如果 s[i]==s[j] 呢？i,j 之间的回文子串又有了更多可能：除了 s[i]!=s[j] 的情况之外，还出现了 s[i…j] 区间中的，以及 s[i]s[j] 组成的回文串。所以我们可以列出状态转移方程：
$$
f(i,j)=max\begin{cases}
f(i+1,j) + f(i,j-1) – f(i+1,j-1) & \text{(s[i]!=s[j])} \\
f(i+1,j) + f(i,j-1) + 1& \text{(s[i]==s[j])}
\end{cases}
$$
所以我们就可以获得代码：

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 1005

using namespace std;

int f[MX][MX],n;
char s[MX];


int work()
{
    int len=strlen(s);
    memset(f,0,sizeof(f));
    for(int i=0;i<len;i++)f[i][i]=1;
    for(int i=1;i<len;i++)
        for(int j=0;j+i<len;j++)
            if(s[j]!=s[j+i])f[j][j+i]=(f[j][j+i-1]+f[j+1][j+i]-f[j+1][j+i-1]+10007)%10007;
            else f[j][j+i]=(f[j][j+i-1]+f[j+1][j+i]+1)%10007;
    return f[0][len-1];
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int w=1;w<=t;w++)scanf("%s",s),printf("Case %d: %d\n",w,work());
    return 0;
}