SGU 132 Accepted !~

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