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 inputabba
4
bb 1
aa 10
ab 2
ba 2
$$$S$$$ is $$$abba$$$. First we choose $$$bb$$$ and get 1 point, then choose $$$aa$$$ and get 10 points. Max is 11 points.
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?
Thanks in advance.
Полный текст и комментарии »