[Noi2010]旅行路线

http://www.zybbs.org/JudgeOnline/problem.php?id=2009

既然说要除草就随便找道题目吧。。。
首先考虑怎么做。。。。为了方便我们看成n<=50,m=3
那么只有3列。。逐格转移的话。。
给每个格子标上它是第几个经过的。
###

#**

*M.

a…

#是用过的点,M是当前点,*是有影响的点。
由于只要每个数x都跟x-1和x+1相邻,就必然能组成一条路径。
所以我们只需要记录*的数是什么,和这个分界线上*中的数与未用过的点相邻情况就可以了。
这样n=25就T了。。。
可以发现很多状态都是打酱油的。。
注意到这个状态已经唯一决定了已经用过的数。那么开个bitset保存用过的数。转移的时候不能用已经用过的数。
状态数就狂减了。。。就能过了

代码:
http://www.ideone.com/oEJNZ