HDU-4632 http://acm.hdu.edu.cn/showproblem.php?pid=4632

浏览数：35 / 时间：2015年06月09日

http://acm.hdu.edu.cn/showproblem.php?pid=4632

题意：

一个字符串，有多少个subsequence是回文串。

别人的题解：

用dp[i][j]表示这一段里有多少个回文串，那首先dp[i][j]=dp[i+1][j]+dp[i][j-1]，但是dp[i+1][j]和dp[i][j-1]可能有公共部分，所以要减去dp[i+1][j-1]。

如果str[i]==str[j]的话，还要加上dp[i+1][j-1]+1。

但是自己却是这样想的，把每个区间都要看是否为回文串，在dp[i][j]=dp[i+1][j]+1。我的想法是错误的，我忽略了每个区间都是一个递推的过程。

比如：aaa，a是一个回文串则外面2个aa只要判断是否相等就可以了就可以。如果区间两头是相等的，则要加上dp[j+1][i-1]+1，因为首尾是可以组成一个回文子串的，而且首尾可以与中间任何一个回文子串组成新的回文子。

其结果要取余，利用来了 dp[i][j]=(dp[i][j]+10007)%10007;

Palindrome subsequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65535 K (Java/Others)
Total Submission(s): 2246 Accepted Submission(s): 895

Problem Description

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence <A, B, D> is a subsequence of <A, B, C, D, E, F>.
(http://en.wikipedia.org/wiki/Subsequence)

Given a string S, your task is to find out how many different subsequence of S is palindrome. Note that for any two subsequence X = <S_x1, S_x2, ..., S_xk> and Y = <S_y1, S_y2, ..., S_yk> , if there exist an integer i (1<=i<=k) such that xi != yi, the subsequence X and Y should be consider different even if S_xi = S_yi. Also two subsequences with different length should be considered different.

Input

The first line contains only one integer T (T<=50), which is the number of test cases. Each test case contains a string S, the length of S is not greater than 1000 and only contains lowercase letters.

Output

For each test case, output the case number first, then output the number of different subsequence of the given string, the answer should be module 10007.

Sample Input

4

a

aaaaa 

goodafternooneveryone 

welcometoooxxourproblems

Sample Output

Case 1: 1 

Case 2: 31 

Case 3: 421 

Case 4: 960

Source

2013 Multi-University Training Contest 4

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[1005][1005];
int main()
{
    int t,k,i,j,g,len,r,p,q,e,m,b;
     char str[1005];
     cin>>q;
     for(r=1;r<=q;r++)
     {
         memset(dp,0,sizeof(dp));
         scanf("%s",str);
         len=strlen(str);
         for(i=0;i<len;i++)
            dp[i][i]=1;//初始化，单个字符肯定是一个回文子串
         for(k=0;k<len;k++)
           {
             for(i=0;i<len-k;i++)
             {
                 j=i+k;
                 dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];////如果区间两头是相等的，则要加上dp[j+1][i-1]+1，
                 //因为首尾是可以组成一个回文子串的，而且首尾可以与中间任何一个回文子串组成新的回文子串
                 if(str[i]==str[j])
                     dp[i][j]+=dp[i+1][j-1]+1;
                 dp[i][j]=(dp[i][j]+10007)%10007;//结果取余。
              }
           }

         printf("Case %d: %d\n",r,dp[0][len-1]);
     }
    return 0;
}
/*
4
a
aaaaa
goodafternooneveryone
welcometoooxxourproblems
Case 1: 1
Case 2: 31
Case 3: 421
Case 4: 960
*/