[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

9 thoughts on “[Noi2010]旅行路线

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>