AT_abc286_c [ABC286C] Rotate and Palindrome

题目描述

给定一个长度为 $N$ 的字符串 $S$。记 $S_i\ (1\leq i \leq N)$ 为 $S$ 从左往右的第 $i$ 个字符。

你可以以任意顺序、任意次数（包括 $0$ 次）进行以下两种操作：

• 支付 $A$ 元，将 $S$ 的最左端字符移动到最右端。也就是说，将 $S_1S_2\ldots S_N$ 变为 $S_2\ldots S_N S_1$。
• 支付 $B$ 元，选择一个 $1$ 到 $N$ 之间的整数 $i$，并将 $S_i$ 替换为任意一个小写英文字母。

请问，最少需要支付多少元才能将 $S$ 变为回文串？

回文串的定义如下：对于某个字符串 $T$，记其长度为 $|T|$，当且仅当对于所有整数 $i$（$1\leq i\leq |T|$），$T$ 的第 $i$ 个字符与倒数第 $i$ 个字符相同，$T$ 才是回文串。

输入格式

输入以如下格式从标准输入读入。

$N$ $A$ $B$ $S$

输出格式

请输出一个整数，表示将 $S$ 变为回文串所需的最小花费。

输入输出样例 #1

输入 #1

5 1 2
rrefa

输出 #1

3

输入输出样例 #2

输入 #2

8 1000000000 1000000000
bcdfcgaa

输出 #2

4000000000

说明/提示

限制条件

• $1\leq N \leq 5000$
• $1\leq A,B\leq 10^9$
• $S$ 是由小写英文字母组成的长度为 $N$ 的字符串
• 除 $S$ 外的所有输入均为整数

样例解释 1

首先进行第 $2$ 种操作 $1$ 次，支付 $2$ 元，将 $i=5$ 的 $S_5$ 替换为 e，此时 $S$ 变为 rrefe。接着进行第 $1$ 种操作 $1$ 次，支付 $1$ 元，$S$ 变为 refer，这是一个回文串。因此，最少支付 $3$ 元即可将 $S$ 变为回文串。无法用 $2$ 元或更少的花费将 $S$ 变为回文串，所以答案是 $3$。

样例解释 2

请注意，答案可能超过 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译