← 返回题目列表

AtCoder · indeednow_2015_finalb_c

C. 回文串联

中文机器翻译题面 查看原题

問題文

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