/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
長さ N の文字列 S が与えられます。S_i\ (1\leq i \leq N) を S の左から i 番目の文字とします。
あなたは以下の 2 種類の操作を好きな順番で 0 回以上好きな回数行うことができます。
-
A 円払う。 S の左端の文字を右端に移動する。すなわち、S_1S_2\ldots S_N を S_2\ldots S_NS_1 に変える。
-
B 円払う。 1 以上 N 以下の整数 i を選び、 S_i を好きな英小文字で置き換える。
S を回文にするためには最低で何円必要ですか？
回文とは
ある文字列 T について、 T の長さを |T| として、全ての整数 i (1 \le i \le |T|) について、 T の前から i 文字目と後ろから i 文字目が同じであるとき、またそのときに限って、 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 番目の操作を 1 回行います。2 円払い、i=5 として S_5 を e で置き換えます。 S は rrefe となります。
次に 1 番目の操作を 1 回行います。1 円払い、S は refer となります。これは回文です。
よって 3 円払うことで S を回文にすることができました。 2 円以下払うことで S を回文にすることは不可能なので、これが答えです。
入力例 2
8 1000000000 1000000000 bcdfcgaa
出力例 2
4000000000
答えは 32 bit 整数に収まらない場合があることに注意してください。
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.