Best Concatenation

题目描述

给定 $N$ 个由数字 $1$ 到 $9$ 以及字符 $X$ 组成的字符串 $S_1, S_2, \ldots, S_N$。 我们将选择一个排列 $P = (P_1, P_2, \ldots, P_N)$，它是 $(1, 2, \ldots, N)$ 的一个置换， 用来构造字符串 $T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}$，其中 $+$ 表示字符串的连接。 然后，我们将计算字符串 $T = T_1T_2\ldots T_{|T|}$（这里 $|T|$ 表示 $T$ 的长度）的“得分”。
得分按下面的 9 步计算，初始得分为 $0$：

对每个满足 $1 \leq i \lt j \leq |T|$、$T_i = X$ 且 $T_j = 1$ 的整数对 $(i, j)$，向得分加 $1$ 点。 对每个满足 $1 \leq i \lt j \leq |T|$、$T_i = X$ 且 $T_j = 2$ 的整数对 $(i, j)$，向得分加 $2$ 点。 对每个满足 $1 \leq i \lt j \leq |T|$、$T_i = X$ 且 $T_j = 3$ 的整数对 $(i, j)$，向得分加 $3$ 点。 $\cdots$ 对每个满足 $1 \leq i \lt j \leq |T|$、$T_i = X$ 且 $T_j = 9$ 的整数对 $(i, j)$，向得分加 $9$ 点。

当 $P$ 可任意选择时，求 $T$ 的最大可能得分。

输入格式

输入按下述格式由标准输入提供： $N$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

输出答案。

3
1X3
59
XXX

71

10
X63X395XX
X2XX3X22X
13
3716XXX6
45X
X6XX
9238
281X92
1XX4X4XX6
54X9X711X1

3010

提示

$2 \leq N \leq 2 \times 10^5$ $N$ 是整数。 $S_i$ 是长度至少为 $1$ 的字符串，由数字 $1$ 到 $9$ 和字符 $X$ 组成。 $S_1, S_2, \ldots, S_N$ 的长度总和至多为 $2 \times 10^5$。当 $P = (3, 1, 2)$ 时，$T = S_3 + S_1 + S_2 =$ $XXX1X359$。 然后，$T$ 的得分按如下计算：

有 $3$ 个整数对 $(i, j)$ 满足 $1 \leq i \lt j \leq |T|$、$T_i = X$ 且 $T_j = 1$； 有 $4$ 个整数对 $(i, j)$ 满足 $1 \leq i \lt j \leq |T|$、$T_i = X$ 且 $T_j = 3$； 有 $4$ 个整数对 $(i, j)$ 满足 $1 \leq i \lt j \leq |T|$、$T_i = X$ 且 $T_j = 5$； 有 $4$ 个整数对 $(i, j)$ 满足 $1 \leq i \lt j \leq |T|$、$T_i = X$ 且 $T_j = 9$。

因此，$T$ 的得分为 $1 \times 3 + 3 \times 4 + 5 \times 4 + 9 \times 4 = 71$，这是可能的最大值。

标签: AtCoder|abc268F

来源

AtCoder|abc268F