# 1. 题面

#### 题目描述

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

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

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

#### 样例

abcab
1 2 4


5


abcab
2 2 1


9


#### 数据范围与提示

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

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

# 2. 题解

• 直接购买：$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)])$

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


#### Remmina

No puzzle that couldn't be solved.