看见SGU 183没有过，就想去过了他……
条件：n=10000 m=100 time limit=250ms
开始的时候，自己想了O(n*m^2)的算法，DP的，O(n*m^2)个状态，O(1)转移，太慢-2s……
后来发现每次新的状态只有m个，其余都是原来的移位，于是通过修改，达到了O(n*m*logm)。其中，O(m*logm)是排序m个数的时间。这样是413ms，慢了一点…… 但是我想不到更快的排序方法了……
于是就改变状态，像题解的那样，结果那样的O(n*m^2)需要4.xs… 改成O(n*m)的，结果还是超时，3xxms.. 正确的算法也需要优化啊……
于是先优化，26xms，再优化，26xms，再优化，终于，只要23xms了……

感觉平时写代码总是写得很烦，写得太复杂了。应该注重代码的简化……

虽然报告上都说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 了…………………… 一周了……