学步园

题目：题目链接

题目的意思就是给你一个字符串，让你找出其中的不同回文子序列的个数有多少。

这道题刚刚拿到手想到上一场多校的1008了，结果那样跑的话就只是第四个样例都卡了好久才出来。所以这样肯定不行，自己一直想到的是枚举，不懂算法。后来看到的是指可以采用区间DP。简单的来说就是用dp[i][j]表示i,j区间内的回文子序列的个数，我们判断的时候，如果发现sp[i]==sp[j]，那么回文子序列就可以加长了。也就是在内部的长度上++，就是dp[i][j]+=dp[i+1][j-1]。就是往两边扩散。

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
using namespace std;
#define N 10007
char sp[1010];
__int64 dp[1010][1010];
int main()
{
    int t;
    scanf("%d", &t);
    int cnt = 1;
    while(t--)
    {
        memset(sp, 0, sizeof(sp));
        memset(dp, 0, sizeof(dp));
        scanf("%s", sp);
        int len = strlen(sp);
        for(int i = 0; i < len; ++i)
            dp[i][i] = 1;
        for(int j = 2; j <= len; ++j)
        {
            for(int k = 0; k < len+1-j; ++k)
            {
                if(sp[k] == sp[j + k - 1])
                    dp[k][j + k - 1] ++;
                else if(k + 1 <= j + k -2)
                    dp[k][j + k - 1] -= dp[k+1][j + k - 2];
                dp[k][j + k - 1] += dp[k + 1][j + k - 1] + dp[k][j + k - 2];
                dp[k][j + k - 1] %= N;
            }
        }
        printf("Case %d: %I64d\n", cnt++, (dp[0][len-1]+N)%N);
    }
    return 0;
}

交的时候WA了一次，是因为取模的时候忘加N了，防止负数的出现嘛。