1. 题面

题目描述

AK 完了 IOI，CGZ 又向着 AK IBO 的目标出发。毕竟不是生竞选手，CGZ 被一道题难住了。

这道题是说，你若想编辑出一个基因 S（只含小写字符），第一步可以先去买下别人编辑好的 S 的一个前缀，若前缀长度为 L，则要花 $x*L$ 万元。然后，你可以做以下两个操作：

1. 将手头的基因复制一遍黏在后面，花费 $y$ 万元。

2. 将手头的基因从某一处切开然后保留前缀，花费 $z$ 万元。

问编辑出 S 最少要花费多少万元？

输入格式

第一行一个字符串 S，保证只含小写字母

第二行三个整数 $x$ ， $y$ ， $z$

输出格式

一行一个整数，表示编辑出基因 S 的最少花费，单位：万元。

样例

输入样例 1

abcab
1 2 4

输出样例 1

输入样例 2

abcab
2 2 1

输出样例 2

数据范围与提示

$1 \leq x,y,z \leq 10$

$|S| \leq 2*10^5$

2. 题解

比较简单的 DP 题

设 $f _ i$ 为构造出前缀 $i$ 的最小代价

设 $z _ i$ 为后缀 $i$ 与原串的最长公共前缀 LCP

有三种转移：

直接购买： $f _ i = x \times i$
倍长：当 $z _ {i + 1} \geq i$ 时，有 $f _ {2i} = f _ i + y$
倍长后删除：当 $f _ {i + k} = f _ i + y + z, (k \in [1, \min(z _ {i + 1}, i)])$

三种转移取 $\min$ 就行了

第三种转移用树状数组后缀最小维护

#include <bits/stdc++.h>

#define NS (200005)
#define lowbit(a) ((a) & (-(a)))

using namespace std;

char s[NS];

int n, X, Y, Z, z[NS], f[NS], t[NS];

void getz()
{
    z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; i += 1)
        if (i > r)
        {
            while (s[i + z[i]] == s[1 + z[i]]) z[i]++;
            l = i, r = i + z[i] - 1;
        }
        else
        {
            z[i] = min(r - i + 1, z[i - l + 1]);
            while (s[i + z[i]] == s[1 + z[i]]) z[i]++;
            if (i + z[i] - 1 >= r) r = i + z[i] - 1, l = i;
        }
}

void push(int x, int d)
{
    while (x) t[x] = min(t[x], d), x -= lowbit(x);
}

int query(int x)
{
    int res = INT_MAX;
    while (x <= n) res = min(res, t[x]), x += lowbit(x);
    return res;
}

int main(int argc, char const* argv[])
{
    scanf("%s%d%d%d", s + 1, &X, &Y, &Z);
    n = strlen(s + 1), getz(), memset(t, 127, sizeof(t)), f[1] = X;
    for (int i = 2; i <= n; i += 1)
    {
        f[i] = min(X * i, query(i));
        if (!(i & 1) && z[(i >> 1) + 1] >= (i >> 1))
            f[i] = min(f[i], f[i >> 1] + Y);
        push(i + min(z[i + 1], i), f[i] + Y + Z);
    }
    printf("%d\n", f[n]);
    return 0;
}

【题解】CGZ AK IBO 扩展 KMP+DP YZOJ – 10039

于2019年2月20日由Remmina发布

1. 题面

题目描述

输入格式

输出格式

样例

数据范围与提示

2. 题解

Remmina

0 条评论

发表回复取消回复

【题解】CGZ AK IBO 扩展 KMP+DP YZOJ – 10039

于2019年2月20日由Remmina发布

1. 题面

题目描述

输入格式

输出格式

样例

数据范围与提示

2. 题解

Remmina

0 条评论

发表回复 取消回复

发表回复取消回复