发表文章

[最新] 「HDU 5677」 ztr loves substring - Manacher + 多重背包

hyp1231 1月前 0

建议访问原文出处,获得更佳浏览体验。
原文出处:http://hyp1231.github.io/2018/07/10/20180710-hdu5677/

题意

给出

链接

HDU5677 ztr loves substring

题解

只与每个串的长度有关,故应先预处理出每个长度的回文串的数量。

使用 Manacher 算法计算出以串的各个位置为中心的最大回文串长度。若以

考虑选出

Hint 1: 转移要求在

记长度为

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

const int N = 128;
const char mid_c = '$';
const char side_c = '@';

int n, k, l;
char s[N][N];
char s2[N << 1];
int len, r[N][N << 1];

void prepare(char s1[]) {
    len = 0;
    s2[len++] = side_c;
    s2[len++] = mid_c;

    int n = strlen(s1);
    for (int i = 0; i < n; ++i) {
        s2[len++] = s1[i];
        s2[len++] = mid_c;
    }
    s2[len + 1] = '\0';
}

void Manacher(char s1[], int id) {
    prepare(s1);
    memset(r[id], 0, sizeof(r[id]));
    int mid = 0, p = 0;
    for (int i = 0; i < len; ++i) {
        int x;
        if (p < i)x = 1;
        else x = std::min(p - i, r[id][2 * mid - i]);
        while (s2[i - x] == s2[i + x]) ++x;
        if (i + x > p) {
            p = i + x;
            mid = i;
        }
        r[id][i] = x;
    }
}

int cnt[N], dp[N][N];
// dp[i][j] 代表 i 个子串拼接成的串的最大长度(不超过 j)

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        memset(cnt, 0, sizeof(cnt));
        memset(dp, 0, sizeof(dp));
        scanf("%d%d%d", &n, &k, &l);
        for (int i = 0; i < n; ++i) {
            scanf("%s", s[i]);
        }
        for (int i = 0; i < n; ++i) {
            Manacher(s[i], i);
            for (int j = 0; j < len; ++j) {
                int tmp = r[i][j] - 1;
                if (tmp <= 0) continue;
                while (tmp > 0) {           // 最长子串逐步去掉侧边字母也是子串
                    ++cnt[tmp];
                    tmp -= 2;
                }
            }
        }
        for (int i = 0; i <= l; ++i) {      // 枚举子串长度
            int sum = cnt[i];               // 长度为 i 的子串数量
            for (int j = 1; sum; j <<= 1) { // 二进制优化
                int mul = std::min(sum, j);
                for (int p = l; p >= mul * i; --p)      // 枚举长度
                    for (int num = mul; num <= k; ++num)// 枚举已选字符串个数
                        if (num == mul || dp[num - mul][p - mul * i] > 0)
                            // 如果本串是第一次被选,或存在选了 p - mul * i 个串的方案
                            dp[num][p] = std::max(dp[num][p], 
                                                  dp[num - mul][p - mul * i] + mul * i);
                sum -= mul;
            }
        }
        printf("%s\n", (dp[k][l] == l ? "True" : "False"));
    }

    return 0;
}
相关推荐
最新评论 (0)
返回
发表文章
hyp1231
文章数
9
评论数
0
注册排名
1307181