U576404 回文串变换

小C最近在学习字符串算法，他想通过一些操作将一个字符串变成回文串

小 C 有一个长度为 $n$（$n$ 为偶数）的小写字母字符串 $S$。他可以通过以下两种操作将 $S$ 变成**回文串**（即对于所有 $1 \leq i \leq n/2$，满足 $S[i] = S[n-i+1]$）： 1. **交换**：交换任意两个位置的字符，每次交换的代价为 $w_{i,j}$（$i$ 和 $j$ 是位置编号，且 $w_{i,j} = w_{j,i}$，$w_{i,i} = 0$）。 2. **替换**：将某个位置的字符 $c_1$ 替换为另一个字符 $c_2$（$c_1 \neq c_2$），代价为 $v_{c_2}$。 小 C 可以**任意组合这两种操作**，目标是让 $S$ 变成回文串，且**总代价最小**。请你帮助他计算出这个最小总代价。

- 第一行：整数 $n$（字符串长度）。 - 第二行：26 个整数，表示替换代价数组 $v$（$v_{c}$ 表示字符 $c$ 的替换代价）。 - 第三行：字符串 $S$。 - 接下来 $n$ 行：每行 $n$ 个整数，表示交换代价矩阵 $w$（$w_{i,j}$ 表示交换位置 $i$ 和 $j$ 的代价）。

- 一个整数，表示最小总代价。

#### 解释 - 交换位置 3 和 5（代价 2），得到 `abaaba`。 - 替换字符 'a' 为 'b'（代价 3），总代价 5，但直接替换更优。 ### 测试点设计 | 测试点 | $n$ | 字符集 | 替换代价 $v$ | 交换代价 $w$ | 预期输出 | 考察点 | |--------|-------|---------------|--------------------|--------------------|----------|----------------------| | 1 | 2 | `a`-`b` | 全 1 | 全 0 | 0 | 已经是回文 | | 2 | 4 | `a`-`d` | 全 1 | 对称矩阵，$w_{i,j}=1$ | 2 | 必须交换 | | 3 | 6 | `a`-`b` | $v_a=1, v_b=2$ | $w_{i,j}=|i-j|$ | 3 | 替换比交换更优 | | 4 | 100 | 全小写字母 | 随机 $1 \leq v_c \leq 100$ | 随机 $1 \leq w_{i,j} \leq 100$ | 动态计算 | 大规模数据验证 | | 5 | 1000 | 全小写字母 | $v_c = c$（ASCII码）| $w_{i,j}=i+j$ | 动态计算 | 极限数据测试 |