[Help] A String Problem Solved By DP + Aho?

Revision en1, by Libraion, 2021-09-24 05:18:03

Given a string $S (|S| \le 100)$ and $n (n \le 1000)$ strings $T_1, T_2, \dots, T_n (|T_i| \le 30)$. Each string $T_i$ has a corresponding point $p_i (1 \le p_i \le 10000)$.

You can do the following operation any number of times (until you cannot choose any substring): Choose a substring in $S$ that is equal to one of $T_i$, delete that substring in $S$, you get $p_i$ points and the remaining characters of $S$ concatenate.

What is the maximum points you can get by doing the operations?

Sample input

I was thinking about a solution using DP and Aho Corasick.

Specifically, let $dp(i, j) =$ the maximum points you can get with the first $i$ characters of $S$ and you are standing at node $j$ in the Trie after doing some operations.

But I came across a problem. When we move from $dp(i, j)$ to $dp(i + 1, k)$, if we jump from node $j$ to node $k$ with suffix link, we lost some information of the prefix that we haven't used in any operation yet.

Could you guys suggest any alternatives? en1 Libraion 2021-09-24 05:18:03 1272 Initial revision (published)