可以在 cnblogs 中阅读。
\(m \le 40\) 的数据范围提示让我们往颜色种类上考虑。
由题每次可以跳 \(1\) 或 \(2\) 格，即存在一条从 \(1\) 到 \(n\) 的路径的充要条件是不存在两个相邻的未激活格。换句话说，对任意两个相邻的格子都必须选择至少一个激活。
任意两个，至少一个，这样的条件使我们联想到最小权点覆盖，我们在 \(1\) 号和 \(n\) 号连自环，其他点相邻的颜色连边，问题转化为求这个图的最小点覆盖。
一个经典结论是最大权独立集 + 最小权点覆盖 = 点权和。最大权独立集可以用记忆化搜索的方式实现。
具体地，设 \(f_S\) 表示集合 \(S\) 的最大权独立集，则有转移：
\[f_S = \max \left\{ f_{S- \left\{ p \right\} },f_{S- \left\{ p \right\} -edge(p)} \right\} \]其中 \(p\) 表示集合中一个点，\(edge(p)\) 表示与 \(p\) 有连边的点集。
但是 \(m \le 40\)，怎么开的下？用 std::map 等工具可以动态开记忆化数组，而状态数的转移满足 \(G(m) \le G(m-1)+G(m-2)\)，最劣情况下是一个斐波那契数列，也就是说 \(G(m) \le O(1.618^m)\)，\(m=40\) 时在 \(2 \times 10^8\) 的级别，而实际上远远跑不满，时间空间都可以接受。
code，使用 __pbds::gp_hash_table 可以跑得更快。
实际上还有一种做法，就是对高 \(20\) 位爆搜，低 \(20\) 位记忆化，这样做保证了复杂度是 \(O(n+2^ \frac{m}{2})\)，而且避免了开 map 等时空消耗大的操作，实测也跑得更快。