HDU 4632 Palindrome subsequence(区间dp)

题目点击打开链接

题目大意：

给一个长度最大10000的字符串，问它有多少个回文子串（不用连续）。

如果取自不同位置的，但是完全相同的子串，也算是不同的回文子串。

分析：

f[i][j] 表示字符串的i~j段共有多少个不同子串
那么f[i][j] = f[i][j-1] + f[i+1][j] - f[i+1][j-1]
如果str[i] == str[j], 那么还要加上
f[i][j] = f[i][j]+f[i+1][j-1]+1;

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MOD = 10007;

int f[MAXN][MAXN], len;
char str[MAXN];

int main(){

    int T;
    int cas = 1;
    scanf("%d", &T);
    while(T--){
         
        scanf("%s", str+1);
        len = strlen(str+1);

        memset(f, 0, sizeof(f));

        for(int i=1; i<=len; ++i) f[i][i] = 1;
        for(int i=1; i<len; ++i){
            if(str[i] == str[i+1]) f[i][i+1] = 3;
            else f[i][i+1] = 2;
        }

        for(int s=3; s<=len; ++s){
            for(int l=1; l+s-1<=len; ++l){
                int r = l + s -1;
                f[l][r] = (f[l][r-1] + f[l+1][r] - f[l+1][r-1] + MOD)%MOD;
                if(str[l] == str[r])
                    f[l][r] = (f[l][r] + f[l+1][r-1] + 1 + MOD)%MOD;
            }
        }
    
        printf("Case %d: %d\n", cas++, f[1][len]);
    }

    return 0;
}