若一个前缀是 $k$-rich 的，且前缀后面出现了 $A,C,G,T$，则这个串是 $(k+1)$-rich 的。
不难发现这个性质充要，即 $(k+1)-rich$ 的串去掉同时包含 $A,C,G,T$ 的最小后缀，剩下的串必定为 $k$-rich。
记 $f_{i,j,S}$ 表示存在 $t\in [1,i]$ 满足 $[1,t]$ 是 $j$-rich，且 $[t,i]$ 出现了 $S$ 中的字符，复杂度 $O(n^22^{|\Sigma|}|\Sigma|)$。
进一步的，根据上述分析，$k$-rich 的充要条件是可以把序列分为 $k$ 段，每段含有 $A,C,G,T$。
尝试去状压，$f_{i,j}$ 表示 $[1,i]$ 分 $j$ 段的最小代价。
区间划分问题，不难发现其满足四边形不等式，$f_{n}(x)$ 是凸的，对于单个 $k$ 可以 WQS 求出。
如果 $f$ 没有其他性质，不能求出整个 $f$，考虑继续分析。
关键观察：由于 $f$ 值域为 $[0,n]$，因此 $f$ 最多只有 $O(\sqrt{n})$ 种不同的斜率。因为假设有 $m$ 种斜率那么 $\max f_{n}(x)\geq \sum_{i=1}^{m} i=O(n^2)$。
类似分治求解，假设当前已经求出 $x_1,x_2$ 处的值，计算斜率 $k=\frac{y_2-y_1}{x_2-x_1}$，然后用斜率 $k$ 切凸包得到 $x_3$（即每分一段减少 $k$ 代价，做不带段数限制的划分 DP），判断 $x_1,x_2,x_3$ 是否共线，不共线就继续向 $x_1\sim x_3$ 和 $x_3\sim x_2$ 递归。
$O(n\sqrt n)$，$4$ 倍常数。
需注意，如果在 DP 时最小化了段数，那么分治过程中斜率应该向上取整，避免 $x_3=x_1$ 导致误判。
