C - Rotate and Palindrome
当前没有测试数据。
C - 旋转和回文
分数：300 分
问题描述
给定一个长度为 $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$ 成为一个回文串？
回文串是什么？
一个字符串 $T$ 是回文串，当且仅当对于所有满足 $1 \le i \le |T|$ 的整数 $i$，$T$ 从左边数第 $i$ 个字符和从右边数第 $i$ 个字符相等时成立，其中 $|T|$ 表示字符串 $T$ 的长度。约束
- $1\leq N \leq 5000$
- $1\leq A,B\leq 10^9$
- $S$ 是一个长度为 $N$ 且由小写英文字母组成的字符串。
- 除了 $S$，输入中的所有值均为整数。
输入
从标准输入读入输入数据，具体格式如下：
输出
输出一个整数作为答案。
5 1 2
rrefa
3
首先，支付 $2$ 日元进行第二种操作：选择 $i=5$，将 $S_5$ 替换为 e。此时 $S$ 变为 rrefe。
然后，支付 $1$ 日元进行第一种操作一次。此时 $S$ 变为 refer，为回文串。
因此，你需要花费 $3$ 日元使得 $S$ 成为回文串。由于小于等于 $2$ 日元是不可能使 $S$ 成为回文串的，所以答案为 $3$。
8 1000000000 1000000000
bcdfcgaa
4000000000
注意答案可能超出 32 位整数的表示范围。