P3294 [SCOI2016] Memorizing Words

Lweb is facing a mountain of English words and falls into deep thought: how can I finish learning quickly and then go play Sanguosha (pinyin)? At this moment, the wise Teacher Feng drifts over from afar. He gives Lweb a planner and a big jar of pickled chili peppers. His planner looks like this: | Index | Word | | ------- | ---- | | $1$ | | | $2$ | | | $\dots$ | | | $n-1$ | | | $n$ | | Then Teacher Feng tells Lweb: I know there are $n$ words you need to learn. We will fill the planner from top to bottom. For the word with index $x$ (the positions $1,\dots ,x-1$ have already been filled): 1. If there exists a word that is its suffix and has not yet been filled into the table, then he needs to eat $n \times n$ chili peppers to learn it. 2. If all of its suffixes have already been filled into the table, and none of the words at positions $1,\dots ,x-1$ is its suffix, then you can remember it by eating $x$ chili peppers. 3. If all of its suffixes have already been filled into the table, and among positions $1,\dots ,x-1$ there exists a word that is its suffix, let the maximum index among its suffixes be $y$. Then you only need to eat $x-y$ chili peppers to remember it. Lweb is a strange kid who goes berserk when he eats spicy things, so please help Lweb find an optimal way to fill the words so that he learns these $n$ words while eating the fewest chili peppers. Formal statement: You need to arrange an order for $n$ strings. Each string incurs a certain cost. For a string $s$ at position $x$: 1. If there exists at least one other string that is a suffix of $s$, and that string’s position is after $s$, then $s$ incurs a cost of $n \times n$. 2. If no other string is a suffix of $s$, then $s$ incurs a cost of $x$. 3. If all strings that are suffixes of $s$ appear before $s$, and the maximum position among them is $y$, then $s$ incurs a cost of $x-y$. Arrange an order for the $n$ strings to minimize the total cost.

Input an integer $n$, the number of words Lweb needs to learn. Then follow $n$ lines, each containing one word (lowercase letters only, and all words are pairwise distinct).

The minimum number of chili peppers Lweb needs to eat.

Constraints: $1\le n\le100000$, and the total length of all strings satisfies $1\le \sum|S| \le510000$. Translated by ChatGPT 5