AT_abc175_f.[ABC175F] Making Palindrome

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

题目大意

有 $N$ 个仅含小写字母的字符串 $S_1,S_2,\cdots,S_N$ 。你需要把从这些字符串中选择一些以任意顺序拼接起来，同一个字符串可以被选择多次。每选择一次 $S_i$ ，你都需要花费 $C_i$ 的代价，也就是说你选择 $S_i$ 所花费的代价为 $C_i$ 与 $S_i$ 被选择的次数之积。求使拼接得到的字符串为回文串所需的最小花费。若不管如何都无法拼接成回文串，输出 -1。

数据范围： $1 \le N \le 50$ ， $1 \le |S_i| \le 20$ ， $1 \le C_i \le 10^9$ 。

输入格式

第一行一个整数 $N$ ，接下来 $N$ 行每行一个字符串 $S_i$ 和一个整数 $C_i$ 。

输出格式

一个整数，为最小代价或 -1。

样例解释

样例 1：我们可以分别选择一次 abc 与 ba，拼接得到回文串 abcba，花费为 $(3+4=7)$ ，为最小值。

样例 2：选择一次 abcab，两次 cba，拼接得到回文串 abcabcbacba，花费为 $(5+3\times2=11)$ ，为最小值。

样例 3：选择 ab 与 cba 花费的代价比仅选择 a 更少。

样例 4：无法拼成回文串。

（翻译 by @CarroT1212）

输入输出样例

输入#1
```
3
ba 3
abc 4
cbaa 5
```
输出#1
```
7
```
输入#2
```
2
abcab 5
cba 3
```
输出#2
```
11
```
输入#3
```
4
ab 5
cba 3
a 12
ab 10
```
输出#3
```
8
```
输入#4
```
2
abc 1
ab 2
```
输出#4
```
-1
```

输入解题思路，AI测评打分。不知道怎么写?

首页