程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 4632 Palindrome subsequence (區間dp 容斥定理)

HDU 4632 Palindrome subsequence (區間dp 容斥定理)

編輯:關於C++

 

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);
    }
}




 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved