CF111C Petya and Spiders - 洛谷
打表题。
下文用 \texttt0 代表没有蜘蛛，\texttt1 代表有蜘蛛，\texttt r 代表右，\texttt l 代表左，\texttt d 代表下，\texttt u 代表上，\texttt s 代表不动。
由于 n\times m\le40，所以 \min\{n,m\}\le6。下文统一令 n\le m。
n=1
构造 \texttt{slr} 循环。即把两边的点都聚向中间。这种方案显然最优。
可以写一个暴力模拟，也可以分类讨论，
- 当 m\bmod3=0 时，状态为 \texttt{100}\times\frac{m}{3}。故答案为 \frac{m}{3}。
- 当 m\bmod3=1 时，状态为 \texttt{100}\times\left\lfloor\frac{m}{3}\right\rfloor+\texttt{1}。故答案为 \left\lfloor\frac{m}{3}\right\rfloor+1。
- 当 m\bmod3=2 时，状态为 \texttt{100}\times\left\lfloor\frac{m}{3}\right\rfloor+\texttt{01}。故答案为 \left\lfloor\frac{m}{3}\right\rfloor+1。
恭喜你，你做到这一步就已经减少了一半的情况。
n=2
n=1 的情况让我们找到了一个策略，即把多个点汇聚到一个点。仅需计算汇聚点数量就可以完成本题。
令汇聚点为 (1,4k+1) 和 (2,4k+3)，k 为正整数。可以直接暴力模拟，也可以通过上述方式推导。