虽然报告上都说132是简单题，但是…… 做起来还是很麻烦的，主要是超时问题。很多人用二进制表示状态，但我用二进制想了n次也没有想通，比如如何计算新增块数？（后来通过阅读周大牛的程序，原来他的状态是三进制的，状态转移/方法是三进制的）于是我先用了3进制，用0表示空格或竖的下面，1表示横的，2表示数的上面。这样的好处是状态少（408个），但是导致了上一行的某个0不能判断是不是空格，严重问题…… 假如2改成竖的下面，导致了同样的问题，只是换到下面一行了…… 后来改用四进制，但是状态太多了…… 最后还是用3进制，但是0表示空格，1表示横的或者竖的下面。这样状态多了（2187=3^7）个，速度慢…… 顶级数据4x s……一天，突然发现了一个优化：在判断能否放入地形的同时能够判断水平空格。这样只要17 s了……原先是预先把两行相容关系存下来（408*408 byte），但是现在，内存不够了(1M)…… 后来想出了位压缩的办法…… 就可以了…… 再加上一些优化…… 只要6 s了……L大牛给了一个优化：预先把一个数对应的三进制存下来。这样，计算两行的可行性变快了50%，但计算两行可行性还是要1.3-1.4 s……（原来2s左右）接下来，一天没有想法。 昨天发现，相容两行的数量很少，只有174k对。今天对此进行优化：开了个大表，枚举这一行的时候，能够直接读出他的可行的上一行（可行就是指2有对应的1）。这样，进行动态规划的时间减少到了很少的时间…… 主要时间花在状态枚举上，这时也只要0.6 s了…… 最终，0.7xx s AC 了…………………… 一周了……