Rotate and Palindrome

题目描述

给你一个长度为 $N$ 的字符串 $S$。令 $S_i\ (1\leq i \leq N)$ 为从左数第 $i$ 个字符。 你可以按任意顺序零次或多次执行下述两种操作：

支付 A 日元（日本的货币单位）。将字符串 $S$ 的最左侧字符移动到最右端。换言之，将 $S_1S_2\ldots S_N$ 变为 $S_2\ldots S_NS_1$。

支付 B 日元。选择一个介于 $1$ 到 $N$ 之间的整数 $i$，并将 $S_i$ 替换为任意小写英文字母。

要把 $S$ 变成回文串，最少需要支付多少日元？

输入格式

输入从标准输入给出，格式如下： $N$ $A$ $B$ $S$

输出格式

输出答案，形式为一个整数。

5 1 2
rrefa

3

8 1000000000 1000000000
bcdfcgaa

4000000000

提示

$1\leq N \leq 5000$ $1\leq A,B\leq 10^9$ $S$ 是一个由小写英文字母组成的长度为 $N$ 的字符串。 输入中除 $S$ 之外的所有值都是整数。首先，支付 $2$ 日元 执行一次第二类操作：令 $i=5$ 将 $S_5$ 替换为 $e$。此时 $S$ 变为 $rrefe$。 然后，支付 $1$ 日元 执行一次第一类操作。此时 $S$ 变为 $refer$，这是一个回文串。 因此，可以用 $3$ 日元 将 $S$ 变为回文串。由于不能用不超过 $2$ 日元 将 $S$ 变为回文串，答案为 $3$。
注意答案可能无法装入 32 位整数类型。

标签: AtCoder|abc286C

来源

AtCoder|abc286C