AT_abc354_g [ABC354G] Select Strings

题目描述

有 $N$ 个仅由小写英文字母组成的字符串 $S_1,S_2,\ldots,S_N$，以及 $N$ 个正整数 $A_1,A_2,\ldots,A_N$。

对于集合 $\lbrace 1,2,\ldots,N \rbrace$ 的某个子集 $T$，如果对于任意 $i,j \in T$ 且 $i \neq j$，都不存在 $S_i$ 是 $S_j$ 的子串的情况，则称 $T$ 为好集合。

请你选择一个好集合 $T$，使得 $\displaystyle\sum_{i\in T}A_i$ 的值最大，并输出这个最大值。

子串的定义：字符串 $S$ 的子串是指通过从 $S$ 的开头删除 $0$ 个或多个字符、从结尾删除 $0$ 个或多个字符后得到的字符串。例如，ab 是 abc 的子串，但 ac 不是 abc 的子串。

输入格式

输入按以下格式从标准输入读入。

$N$
$S_1$
$S_2$
$\vdots$
$S_N$
$A_1\ A_2\ \ldots\ A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4
atcoder
at
coder
code
5 2 3 4

输出 #1

6

输入输出样例 #2

输入 #2

10
abcd
abc
ab
a
b
c
d
ab
bc
cd
100 10 50 30 60 90 80 70 40 20

输出 #2

260

说明/提示

限制条件

• $1 \leq N \leq 100$
• $S_i$ 由小写英文字母组成
• $1 \leq |S_i|$
• $|S_1|+|S_2|+\ldots+|S_N| \leq 5000$
• $1 \leq A_i \leq 10^9$

样例解释 1

作为好集合的 $T$ 及其对应的 $\displaystyle\sum_{i\in T}A_i$ 如下：

• 当 $T = \lbrace 1 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 5$
• 当 $T = \lbrace 2 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 2$
• 当 $T = \lbrace 3 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 3$
• 当 $T = \lbrace 4 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 4$
• 当 $T = \lbrace 2,3 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 5$
• 当 $T = \lbrace 2,4 \rbrace$ 时，$\displaystyle\sum_{i\in T}A_i = 6$

其中最大值为 $6$，因此输出 $6$。

由 ChatGPT 4.1 翻译