首页 > ACM题库 > HDU-杭电 > HDU 4632-Palindrome subsequence[解题报告]HOJ
2015
09-17

HDU 4632-Palindrome subsequence[解题报告]HOJ

Palindrome subsequence

问题描述 :

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 = <Sx1, Sx2, …, Sxk> and Y = <Sy1, Sy2, …, Syk> , if there exist an integer i (1<=i<=k) such that xi != yi, the subsequence X and Y should be consider different even if Sxi = Syi. Also two subsequences with different length should be considered different.

输入:

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.

输出:

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.

样例输入:

4
a
aaaaa
goodafternooneveryone
welcometoooxxourproblems

样例输出:

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

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 1005;
int dp[maxn][maxn];
char s[maxn];
int main(){
	int t;
	int ca = 1;
	scanf("%d",&t);
	while(t --){
		scanf("%s",s);
		int len = strlen(s);
		for(int l = 0;l < len;l ++){
			for(int i = 0;i + l < len;i ++){
				if(l == 0)dp[i][i] = 1;
				else if(l == 1){
					if(s[i] == s[i + 1])dp[i][i + 1] = 3;
					else dp[i][i + 1] = 2;
				}
				else {
					dp[i][i + l] = dp[i + 1][i + l] + dp[i][i + l - 1] - dp[i + 1][i + l - 1];
					if(s[i] == s[i + l])dp[i][i + l] += dp[i + 1][i + l - 1] + 1;
					dp[i][i + l] = (dp[i][i + l] + 10007) % 10007;
				}
				//printf("i = %d j = %d dp = %d\n",i,i + l,dp[i][i + l]);
			}
		}
		printf("Case %d: %d\n",ca ++,dp[0][len - 1]);
	}
	return 0;
}