24 人解决,34 人已尝试。
29 份提交通过,共有 142 份提交。
5.2 EMB 奖励。
单点时限: 1.0 sec
内存限制: 512 MB
阿屈和室友蓬蓬最近在玩一种单词游戏,游戏规则如下:
- 开始时会给出 $N$ 个单词 $S_1, S_2, …, S_N$
- 每个玩家选择至少一个单词(可以重复选则某个单词 $S_i$),拼接形成回文串
- 率先得到回文串的玩家获胜
蓬蓬发现他每次都打不过阿屈,于是他修改了游戏规则:
- 每个单词 $S_i$ 赋予一个值 $1\le C_i \le 10^9$,每选择一次 $S_i$ 就要付出 $C_i$ 的代价
- 构成回文串且所用代价最小的玩家获胜
阿屈虽然能很快得到回文串,但却不擅长得到最小代价回文串,这撼动了他在单词游戏中的统治地位。你能帮助阿屈计算出构成回文串的最小代价吗?
第一行一个正整数 $N$ ($1\le N \le 100$)。
接下来 $N$ 行,每行一个字符串 $S_i$ ($1\le |S_i| \le 60$) 以及一个正整数 $C_i$ ($1\le C_i \le 10^9$) 表示选择该字符串的代价。
输出一个正整数 cost,表示阿屈用所给单词 $S_1, S_2, …, S_N$ 构成回文串的最小代价。若无法构成回文串,输出 -1。
4 ab 5 cba 3 a 12 ab 10
8
2 abc 1 ab 2
-1
2 abcab 5 cba 3
11
$1\le N\le100$
$1\le|S_i|\le 60$
$1\le C_i \le 10^9$
$S_i$ 只包含小写字母
在样例 1 中,可以选择 a
直接构成回文串,所需代价为 12,但选择 ab
和 cba
构成回文串 abcba
的代价为 8。
在样例 2 中,无法构成回文串,输出 -1。
在样例 3 中,选择 abcab
一次、cba
两次,构成回文串 abcab|cba|cba
,最小代价为 11。
24 人解决,34 人已尝试。
29 份提交通过,共有 142 份提交。
5.2 EMB 奖励。
创建: 1 年,7 月前.
修改: 1 年,7 月前.
最后提交: 8 月,1 周前.
来源: N/A