分数: 300 点
问题陈述
给你一个字符串 S 长度 N。 让 S_i\ (1\leq i \leq N) 是 i- 第一个字符 S 从左边开始。
您可以按任意顺序执行以下两种操作零次或多次:
-
支付 A 日元(日本货币)。 移动最左边的字符 S 到右端。 换句话说,改变 S_1S_2\ldots S_N to S_2\ldots S_NS_1.
-
支付 B 日元。 选择一个整数 i 之间 1 和 N,并替换 S_i 与任何小写英文字母。
您需要支付多少日元才能制作 S 回文?
什么是回文?
一个字符串 T 是回文当且仅当 i从左边数第一个字符和 i从右边算起的第一个字符对于所有整数都是相同的 i (1 \le i \le |T|),其中 |T| 是长度 T.约束
- 1\leq N \leq 5000
- 1\leq A,B\leq 10^9
- S 是一个长度为的字符串 N 由小写英文字母组成。
- 输入中的所有值,除了 S 是整数。
输入
输入由标准输入按以下格式给出:
N A B S
输出
将答案打印为整数。
示例输入 1
5 1 2 rrefa
示例输出 1
3
一、付款 2 日元执行一次第二种操作:让 i=5 替换 S_5 与 e. S 现在 rrefe.
然后,付款 1 日元执行第一种操作一次。 S 现在 refer,这是一个回文。
因此,您可以使 S 回文 3 日元。 既然你无法使 S 回文 2 日元或更少, 3 就是答案。
示例输入 2
8 1000000000 1000000000 bcdfcgaa
示例输出 2
4000000000
请注意,答案可能不适合 32- 位整数类型。