102862: [AtCoder]ABC286 C - Rotate and Palindrome
Description
Score : $300$ points
Problem Statement
You are given a string $S$ of length $N$. Let $S_i\ (1\leq i \leq N)$ be the $i$-th character of $S$ from the left.
You may perform the following two kinds of operations zero or more times in any order:
-
Pay $A$ yen (the currency in Japan). Move the leftmost character of $S$ to the right end. In other words, change $S_1S_2\ldots S_N$ to $S_2\ldots S_NS_1$.
-
Pay $B$ yen. Choose an integer $i$ between $1$ and $N$, and replace $S_i$ with any lowercase English letter.
How many yen do you need to pay to make $S$ a palindrome?
What is a palindrome?
A string $T$ is a palindrome if and only if the $i$-th character from the left and the $i$-th character from the right are the same for all integers $i$ ($1 \le i \le |T|$), where $|T|$ is the length of $T$.Constraints
- $1\leq N \leq 5000$
- $1\leq A,B\leq 10^9$
- $S$ is a string of length $N$ consisting of lowercase English letters.
- All values in the input except for $S$ are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A$ $B$ $S$
Output
Print the answer as an integer.
Sample Input 1
5 1 2 rrefa
Sample Output 1
3
First, pay $2$ yen to perform the operation of the second kind once: let $i=5$ to replace $S_5$ with e. $S$ is now rrefe.
Then, pay $1$ yen to perform the operation of the first kind once. $S$ is now refer, which is a palindrome.
Thus, you can make $S$ a palindrome for $3$ yen. Since you cannot make $S$ a palindrome for $2$ yen or less, $3$ is the answer.
Sample Input 2
8 1000000000 1000000000 bcdfcgaa
Sample Output 2
4000000000
Note that the answer may not fit into a $32$-bit integer type.
Input
题意翻译
给出一个字符串，有两种操作： + 花费 A ，把串的第一位放到最后一位 + 花费 B ，修改串的一个字母 求把原串变成回文串的最小代价。 输入： 先输入 $n,A,B$ ，第二行字符串 $S$Output
分数：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 成为回文字符串？
什么是回文字符串？
A 字符串 $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，这是一个回文字符串。
因此，你可以用 3 日元使 S 成为回文字符串。 由于你无法用 2 日元或更少的金额使 S 成为回文字符串，所以答案是 3。
样例输入 2
8 1000000000 1000000000 bcdfcgaa
样例输出 2
4000000000
注意，答案可能不