Ruins He's house

这题还是看了官方的解题报告才明白怎么做的，动态规划加记忆化搜索。

$dp[n][k]$ 代表 $n$ 个人中有 $k$ 个人都拿错信件的状态数目，

• 当 $n=k=0$ 时：$dp[n][k]=1$
• $n=0$ 时：$dp[n][k]=0$
• $k=0$ 时：$dp[n][k]=n \times dp[n-1][k]$
• 否则：$dp[n][k]=(n-k) \times (dp[n-2][k-1]+dp[n-1][k])+(k-1) \times (dp[n-2][k-2]+dp[n-1][k-1])$

注意：当 $k=1$ 时，没有后半部分

这题要转换一下思维来做，从第一行开始，枚举同一行相邻的两个格子，如果不是同一类型 (即不同时为水或者同时为陆地)，就判定这条边是合法的。

对于剩余的边，从第二行开始，判断每个格子上方的边是否符合处于两种类型格子之间即可，这样就可以不重复地把全部的边都检查完，由于边缘的边都不算，也让我们很方便的不需要考虑太多的边界条件。

简单题，赛后看了一下好多人对数组进行了排序，然后再进行枚举判断，我觉得这样并不是最好的方法，我的方法是开一个 bool 型的数组，has[i] 代表第 $i$ 天如果冲突，则需要改计划，这样每次对连续的 $k$ 天进行枚举，用 $O(nk)$ 的时间可以直接 check 完，每次检查 $k$ 子串后，判断答案，如果比现有答案小，这更新答案，最后返回即可。

做过 TC 的比赛感觉上了相对来说，Code Forces 的比赛应该会简单一些，不过很可惜，那晚第三题并没有拍出来，可能是时间不够了，卡在第一题上太久，有点悲剧。。。。

最近开始拍 TC 的陈题，这应该算是第二套 AK 的题目了吧，题目不是很难，很适合练习拍代码的速度。。。