题目：AT_abc264_g
题意
-
有 \(n\) 个小写字母字符串 \(T_i(1 \le i \le n)\) 和数组 \(P\)，一个非空且只包含小写字母的字符串 \(S\) 的优美度为 \(\sum\limits_{i = 1}^{n}T_i \ 在 \ S \ 中的出现字数 \times P_i\)。问优美度最大值，可以无穷大输出
Infinity。 -
数据范围：\(1 \le n \le 18278, T_i 长度不大于 3 且两两不同，-10^9 \le P_i \le 10^9\)
思路
-
首先 \(n\) 给了一个奇怪的数值，我们经过一些尝试发现 \(18278 = 26 + 26^2 + 26^3\)，说明每个满足要求的 \(T\) 都可能在里面。
-
闲言少叙，下面进入正题。可以发现有状态 \((i, j, k, w)\) 表示当前后三个字符为 \(i,j,k\) 那么 \((len, i, j, k, w)\) 可以转移到 \((len + 1, j, k, l, w + W(k) + W(jk) + W(ijk))\)，\(W(s)(s 为字符串)\) 表示 \(s\) 在 \(n\) 个字符中是否出现过，出现就返回对应 \(P_i\)，否则返回 \(0\)。那么我们明显可以做 \(DP\)。
-
但是其实发现如果把 \(W(k) + W(jk) + W(ijk)\) 看做边权，我就是在做
bellman-ford，而我们发现如果答案为无穷大，就是出现了正环，而bellman-ford既然可以用最短路判负环，那当然可以用最长路判正环。 -
但是这个算法的时间复杂度是不被接受的，
bellman-ford的时间复杂度为 \(O(点数 \times 边数)\)，在这里就是 \(26^3 \times 26^4\)（\(w\) 是最优化属性），是会炸掉的。 -
那该怎么办呢。事实上我们发现 \(26^5\) 是可以过掉的，我们可以考虑一个新的状态：\(f_{i,j}\) 表示后两位为 \(ij\) 的最大答案。那么 \(f_{i,j}\) 可以转移到到 \(f_{j,k}\)，正好也可以把后三位得到，时间复杂度过掉了。
-
注意要把只有一个字符的字符串的答案处理好，\(W()\) 可以用进制得到。
-
时间复杂度：\((26^5)\)。