HDU 4632 Palindrome subsequence (區間dp 容斥定理)
Palindrome subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65535 K (Java/Others)
Total Submission(s): 2610 Accepted Submission(s): 1050
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 is a subsequence of .
(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 =
x1, Sx2, ..., Sxk> and Y = y1, 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.
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
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4632
題目大意：給一個字符串，求其所有回文子串的個數，字符位置不同屬於不同的回文子串
題目分析：很熟悉的一道dp，貌似是編程之美資格賽的一題，原來是曾經多校的原題啊。。。我們從左向右枚舉區間，對於每個區間從外向內算，dp[i][j]表示從i到j的子串中回文子串的個數如果s[i] == s[j]，則dp[i][j] += dp[i - 1][j + 1] + 1，另外dp[i][j] = dp[i - 1][j] + dp[i][j + 1] - dp[i - 1][j + 1]，這裡相當於一個容斥，去掉重復的部分，最後的答案為dp[len][1]
#include
#include
int const MAX = 1005;
int const MOD = 10007;
char s[MAX];
int dp[MAX][MAX];
int main()
{
int T;
scanf(%d, &T);
for(int ca = 1; ca <= T; ca++)
{
printf(Case %d: , ca);
memset(dp, 0, sizeof(dp));
scanf(%s, s + 1);
int len = strlen(s + 1);
for(int i = 1; i <= len; i++)
{
for(int j = i; j >= 1; j--)
{
if(i == j)
{
dp[i][j] = 1;
continue;
}
if(s[i] == s[j])
dp[i][j] += dp[i - 1][j + 1] + 1;
dp[i][j] += (5 * MOD + dp[i - 1][j] + dp[i][j + 1] - dp[i - 1][j + 1]) % MOD;
}
}
printf(%d
, dp[len][1] % MOD);
}
}
