問題文
Indeed 员工 A 先生正在磨练他的字符串处理技能。 A先生目前正在解决的问题如下。
我想通过连接几个回文来创建一个字符串。长度 使用 i 回文可以降低成本。 C_i 需要。此时,字符串 求创建 S 所需的最小成本总和。然而,回文是一串无论从前面读还是从后面读都相同的字符串。另外,同样的回文 2 请注意,即使您多次使用它,费用也将等于您使用它的次数。
然而,A先生却无法解决这个问题。请为A先生写一个程序来解决这个问题。
入力
输入是按以下格式从标准输入给出的。
N S C_1 C_2 ... C_N
- 1 字符串 给出了 S 长度的整数 N (1 ≦ N ≦ 5000) 。 表示
- 2 字符串
给出了 S 。
表示S 是一个小写字母 (
仅由
a-z) 长度仅包含 它是一个 N 字符串。 字符 - 3 行表示使用回文的成本。 N 整数由空格分隔。其中 i (1 ≦ i ≦ N) 第一个整数 C_i (1 ≦ C_i ≦ 10^5) 是长度 表示使用 i 回文的成本。
部分点
针对此问题设置了部分分数。
- N ≦ 200 的数据集 如果您正确回答 1 ,40 点。 如果您正确回答了所有满足
- 如果所有测试用例都回答正确,除上述之外, 60 点。 如果您正确回答了所有满足
出力
连接几个回文来创建一个字符串 制作 S 时所需成本总和的最小值为 1 行输出。在输出末尾插入换行符。
入力例1
9 indeednow 1 1 1 1 1 1 1 1 1
出力例1
4
在此输入示例中,i + ndeedn + o + w 那样连接,成本就会降低。 4 。
对于
入力例2
9 indeednow 10 4 1 99 99 99 99 99 99
出力例2
74
在此输入示例中,i + ndeedn + o + w 那样连接,成本就会降低。 129 然而,
i + n + d + ee + d + n + o + w 那样连接,成本就会降低。 74 。
对于
入力例3
12 abcbaabcbcbc 20 13 15 29 38 43 76 58 23 128 99999 100000
出力例3
78