提供一个简单的 DP 思路。
## 0x01 重点信息
可以先找出题目中的一些重点信息。
- 字符串中只有 $G$ 与 $H$。
- $N$ 很大（$2 \leq N \leq 10^5$），但 $C$ 很小（$1 \leq C \leq 18$）。
## 0x02 思路
既然字符串中只有 $G$ 与 $H$，我们不妨将字符串转化为二进制数字（如 $1$ 代表 $G$，$0$ 代表 $H$），转化为数字会使我们的操作更加便捷。
接下来思考如何做。
易想到一个 $O(N^2C)$ 的朴素做法，但是 $N^2$ 的时间代价过于大了。
$N$ 很大（$2 \leq N \leq 10^5$），但 $C$ 很小（$1 \leq C \leq 18$），所以我们可以尝试把复杂度重心放到 $C$ 上。
那么我们就要把思考的方向从每个串之间转到每位之间了。
但单独对于每一位考虑没有意义，那样是不能优化时间复杂度的（毕竟原来的朴素思路也是一位一位比对）。
于是我们考虑多位（区间）。
进一步，我们去考虑前缀。
设 $f_{i,j}$ 表示数字 $i$（每个数字化为二进制后对应一个字符串）的前 $j$ 位与其他字符串的最大差异度。
由于我们一位一位考虑，显然有：
$$
f_{i,j} = max(f_{i,j-1},f_{k,j-1}+1)
$$
其中 $k$ 为前 $j-1$ 位与 $i$ 相同，第 $j$ 位与 $i$ 相反，剩下位乱搞的数字。
那么 $f_{x,c}$ 即为每问所求。
时间复杂度 $O(2^CC)$，完全没有问题。
标签：USACO23OPEN,数字,Field,复杂度,一位,leq,字符串,Day From： https://www.cnblogs.com/2021cjx-akioi/p/USACO23OPEN_1.html