Palindrome subsequence

HDU4632 Palindrome subsequence

标签： 区间DP 容斥原理

---

题目描述

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.

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.

输出描述

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

题解

基础的区间DP，这里转移模式采用逐个转移。

f[i][j] = (f[i][j - 1] + f[i + 1][j] - f[i + 1][j - 1] + p) % p;

注意中间会被重复统计，所以应该减去。
那么如果两端字符相等，则

if(s[i] == s[j]) f[i][j] = (f[i][j] + f[i + 1][j - 1] + 1) % p;

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define N 1100
#define p 10007
#define ll long long
using namespace std;

int t;
ll f[N][N];
char s[N];

int main()
{
    scanf("%d", &t);
    for(int a = 1; a <= t; a ++)
    {
        scanf("%s", s);
        int len = strlen(s);
        memset(f, 0, sizeof(f));
        for(int i = 0; i <= len; i ++) f[i][i] = 1;
        for(int l = 2; l <= len; l ++)
            for(int i = 0; i < len - l + 1; i ++)
            {
                int j = i + l - 1;
                f[i][j] = (f[i][j - 1] + f[i + 1][j] - f[i + 1][j - 1] + p) % p;
                if(s[i] == s[j]) f[i][j] = (f[i][j] + f[i + 1][j - 1] + 1) % p;
            }
        printf("Case %d: %lld\n", a, f[0][len - 1]);
    }
    return 0;
}

心得

感觉跟回文序列有关的区间DP都可以采用逐次转移法（纯口胡莫信…溜了溜了）