首先，我们把 \(s\) 翻转。
考虑 dp，\(f_{i, j, k}\) 表示到了第 \(i\) 个字符，操作了 \(j\) 个字符，最大的字符为 \(k\) 的最大值。
转移时枚举 \(i-1\) 的最大字符 \(\ell(0\le\ell<5)\)。
不操作第 \(i\) 个字符；
- \(f_{i, j, k}=\max\{f_{i-1, j, \ell} + w\}\)。
操作第 \(i\) 个字符。
- 我们稍加思考，可以发现一定是操作成字符 \(k\)。
证明：
如果 \(k>\ell\)，只有将第 \(i\) 个字符操作成 \(k\)，才能满足定义中的条件。
如果 \(k=\ell\)，将其变成 \(<\ell\)，则权值为负，肯定不优。- \(f_{i, j, k}=\max\{f_{i-1,j-1,\ell}+w\}\)。