区间DP。。。。

Palindrome subsequence

4
a
aaaaa
goodafternooneveryone
welcometoooxxourproblems

Case 1: 1
Case 2: 31
Case 3: 421
Case 4: 960

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

using namespace std;

const int MOD=10007;
const int maxn=1100;

int dp[maxn][maxn],n;
char str[maxn];

int main()
{
    int T_T,cas=1;
    scanf("%d",&T_T);
while(T_T--)
{
    scanf("%s",str);
    n=strlen(str);
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++) dp[i][i]=1;

    for(int i=2;i<=n;i++)
    {
        for(int j=0;j+i-1<n;j++)
        {
            int from=j,to=j+i-1;

            if(str[from]==str[to])
            {
                dp[from][to]++;
            }
            else
            {
                dp[from][to]-=dp[from+1][to-1];
            }
            dp[from][to]+=dp[from+1][to]+dp[from][to-1];
            dp[from][to]%=MOD;
        }
    }

    printf("Case %d: %d\n",cas++,(dp[0][n-1]+MOD)%MOD);
}
    return 0;
}

HDOJ 4632 Palindrome subsequence,布布扣,bubuko.com

HDOJ 4632 Palindrome subsequence

原文：http://blog.csdn.net/u012797220/article/details/22541495