103546: [Atcoder]ABC354 G - Select Strings
Description
Score : $625$ points
Problem Statement
You are given $N$ strings $S_1, S_2, \ldots, S_N$ consisting of lowercase English letters and $N$ positive integers $A_1, A_2, \ldots, A_N$.
A subset $T$ of $\lbrace 1, 2, \ldots, N \rbrace$ is called a good set if there is no pair $i, j \in T$ such that $S_i$ is a substring of $S_j$.
Find the maximum possible value of $\displaystyle \sum_{i \in T} A_i$ for a good set $T$.
What is a substring?
A substring of a string $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$. For example,ab is a substring of abc, but ac is not a substring of abc.
Constraints
- $1 \leq N \leq 100$
- $S_i$ is a string consisting of lowercase English letters.
- $1 \leq |S_i|$
- $|S_1| + |S_2| + \ldots + |S_N| \leq 5000$
- $1 \leq A_i \leq 10^9$
Input
The input is given from Standard Input in the following format:
$N$ $S_1$ $S_2$ $\vdots$ $S_N$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print the answer.
Sample Input 1
4 atcoder at coder code 5 2 3 4
Sample Output 1
6
The possible good sets $T$ and their corresponding $\displaystyle \sum_{i \in T} A_i$ are as follows:
- $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$
The maximum among them is $6$, so print $6$.
Sample Input 2
10 abcd abc ab a b c d ab bc cd 100 10 50 30 60 90 80 70 40 20
Sample Output 2
260
Output
问题描述
你被给出了包含小写字母的字符串$S_1, S_2, \ldots, S_N$以及$N$个正整数$A_1, A_2, \ldots, A_N$。
一个子集$T$，如果不存在$i, j \in T$使得$S_i$是$S_j$的子串，则称$T$为一个好集。
找出好集$T$的最大可能值$\displaystyle \sum_{i \in T} A_i$。
什么是子串？
一个字符串$S$的子串是从$S$的开头删除零个或多个字符，以及从$S$的末尾删除零个或多个字符后所得到的字符串。 例如，ab是abc的子串，但ac不是abc的子串。
限制条件
- $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$
输入
输入数据通过标准输入给出以下格式：
$N$ $S_1$ $S_2$ $\vdots$ $S_N$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
打印答案。
样例输入1
4 atcoder at coder code 5 2 3 4
样例输出1
6
可能的好集$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$。
样例输入2
10 abcd abc ab a b c d ab bc cd 100 10 50 30 60 90 80 70 40 20
样例输出2
260