Select Strings

题目描述

你有 $N$ 个由小写英文字母组成的字符串 $S_1, S_2, \ldots, S_N$ 和 $N$ 个正整数 $A_1, A_2, \ldots, A_N$。 若集合 $T \subseteq \lbrace 1, 2, \ldots, N \rbrace$ 满足不存在一对 $i, j \in T (i \neq j)$ 使得 $S_i$ 是 $S_j$ 的子串，则称 $T$ 为一个 良好集合。 求良好集合 $T$ 的 $\displaystyle \sum_{i \in T} A_i$ 的最大可能值。

输入格式

输入按下述格式由标准输入给出： $N$ $S_1$ $S_2$ $\vdots$ $S_N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

4
atcoder
at
coder
code
5 2 3 4

6

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

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$可能的良好集合 $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$。

标签: AtCoder|abc354G

来源

AtCoder|abc354G