AT_abc344_d.[ABC344D] String Bags

普及/提高-

通过率：0%

AC君温馨提醒

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

题目描述

你一开始拥有一个空字符串 $S$ 。
此外，你还有编号为 $1,2,\dots,N$ 的若干个袋子，每个袋子中装有若干字符串。
袋子 $i$ 中有 $A_i$ 个字符串，分别为 $S_{i,1},S_{i,2},\dots,S_{i,A_i}$ 。

接下来，你需要对 $i=1,2,\dots,N$ 依次进行如下操作：

从以下两种行为中任选其一：
- 支付 $1$ 元，从袋子 $i$ 中恰好选择一个字符串，将其连接到 $S$ 的末尾。
- 什么都不做。

给定字符串 $T$ ，请你求出最终使 $S$ 与 $T$ 完全相同所需的最小金额。
如果无论如何都无法使最终的 $S$ 与 $T$ 相同，请输出 $-1$ 。

输入格式

输入按以下格式从标准输入给出。

$T$ $N$ $A_1$ $S_{1,1}$ $S_{1,2}$ $\dots$ $S_{1,A_1}$ $A_2$ $S_{2,1}$ $S_{2,2}$ $\dots$ $S_{2,A_2}$ $\vdots$ $A_N$ $S_{N,1}$ $S_{N,2}$ $\dots$ $S_{N,A_N}$

输出格式

请输出一个整数，表示所需的最小金额。

输入输出样例

输入#1

abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de

输出#1

输入#2
```
abcde
3
2 ab abc
3 f c bcde
1 e
```
输出#2
```
-1
```

输入#3

aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc

输出#3

说明/提示

限制条件

$T$ 是一个长度在 $1$ 到 $100$ 之间的仅包含小写英文字母的字符串。
$N$ 是 $1$ 到 $100$ 之间的整数。
$A_i$ 是 $1$ 到 $10$ 之间的整数。
$S_{i,j}$ 是长度在 $1$ 到 $10$ 之间的仅包含小写英文字母的字符串。

样例解释 1

例如，可以按如下方式用 $2$ 元使最终的 $S$ 与 $T$ 相同，并且这就是所需金额的最小值。

对于 $i=1$ ，从袋子 $1$ 中选择 abc，连接到 $S$ 的末尾。此时 $S=$ abc。
对于 $i=2$ ，什么都不做。
对于 $i=3$ ，从袋子 $3$ 中选择 de，连接到 $S$ 的末尾。此时 $S=$ abcde。

样例解释 2

无论如何都无法使最终的 $S$ 与 $T$ 相同，因此请输出 $-1$ 。

由 ChatGPT 4.1 翻译

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

首页