首页 > 其他 > 详细

编程之美2015 #2 回文字符序列

时间:2015-04-20 23:57:06      阅读:391      评论:0      收藏:0      [点我收藏+]

题目:

时间限制:2000ms
单点时限:1000ms
内存限制:256MB

描述

给定字符串,求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。例如字符串aba中,回文子序列为"a", "a", "aa", "b", "aba",共5个。内容相同位置不同的子序列算不同的子序列。

输入

第一行一个整数T,表示数据组数。之后是T组数据,每组数据为一行字符串。

输出

对于每组数据输出一行,格式为"Case #X: Y",X代表数据编号(从1开始),Y为答案。答案对100007取模。

数据范围

1 ≤ T ≤ 30

小数据

字符串长度 ≤ 25

大数据

字符串长度 ≤ 1000

样例输入

5
aba
abcbaddabcba
12111112351121
ccccccc
fdadfa

样例输出

Case #1: 5
Case #2: 277
Case #3: 1333
Case #4: 127
Case #5: 17

本题我采用动态规划的思想,f[i][j][k]=∑f[i+1][j-1][k-2];但是超时了。

我的答案:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longestPalindrome(const string s, int n) {
    if (n == 0)
        return 1;
    if (n == 1)
        return s.size();
    int count = 0;
    for (int j = 0; j < s.size() - n + 1; j++){
        for (int k = j + n - 1; k < s.size(); k++){
            if (s[j] == s[k]){
                count += longestPalindrome(s.substr(j + 1, k - j - 1), n - 2);
            }
        }
    }
    return count;
}
int getPalindromeList(const string s){
    int count = s.size();
    for (int i = 2; i <= s.size(); i ++){
        count += longestPalindrome(s, i);
    }
    return count;
}
int main(void){
    int mod = 100007;
    int dataNum;
    cin >> dataNum;
    vector<int> answer;
    for (int i = 0; i < dataNum; i++){
        string str;
        cin >> str;
        answer.push_back(getPalindromeList(str));
    }
    for (int i = 0; i < dataNum; i++)
        cout << "Case #" << i + 1 << ": " << answer[i] << endl;
    return 0;
}

最优答案:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

#define mxn 200005
#define LL long long
#define MP make_pair
#define REP(i, a, b) for (int i = a; i <= b; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)

#define mod 100007

int dp[1005][1005];
char s[1005];

int F(int l, int r) {
    if (dp[l][r] != -1) return dp[l][r];
    if (l > r) return dp[l][r] = 0;
    if (l == r) return dp[l][r] = 1;
    int& ret = dp[l][r];
    ret = (F(l + 1, r) + F(l, r - 1)) % mod;
    if (s[l] == s[r]) ++ret;
    else ret -= F(l + 1, r - 1);
    ret = (ret + mod) % mod;
    return ret;
}

int main()
{
    int cas = 0, t;

    scanf("%d", &t);
    while (t--) {
        memset(dp, -1, sizeof(dp));
        scanf("%s", s + 1);
        int ans = F(1, strlen(s + 1));
        printf("Case #%d: %d\n", ++cas, ans);
    }
    return 0;
}

 

 

编程之美2015 #2 回文字符序列

原文:http://www.cnblogs.com/Scorpio989/p/4442866.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!