显然，对于此题，如果按题解所说，设 $dp[i][j][state]$ 为 $(i,j)$ 位置，状态为 $state$ 的方案数。那么 $state$ 要枚举到 $3^{m+1}$（$m$ 列，$m+1$ 个插头），如果用 $4$ 进制优化的话，那就要枚举到 $4^{m+1}$。显然，对于 $m=12$ 的数据是存不下的。但由于轮廓线上有很多无用状态，所以考虑记录所有的合法状态并存储下来（类似离散化或 map），但是如何计算一条轮廓线上最多有多少个合法状态呢？

换言之，如何计算下式的最大值：

$\sum_{i=1}^{\frac{m}{2}}C_m^i\times C_{m-i}^i$

至于我怎么发现的？我发现我合法状态开到 $4^{m+1}$ 过了但是在学校 OJ 上没过……