C - Palindrome Concatenation Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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