插头DP 专题训练

发布于 2018-01-26  3.78k 次阅读


做了接近一天插头DP,感觉大体上比较理解了。

首先,这玩意主要是处理棋盘上路径/回路的计数或是最值查询,数据范围的特点是列数比较小(大概在10左右),行数可以稍多一些,有时候数据不保证行数大于列数,需要对矩阵进行旋转后再做。

主要是引入了插头的概念,DP时逐格转移,并状压轮廓线上m+1个插头的状态(m为列数),轮廓线以上部分为已知,并转移第j个和第j+1个插头(插头范围1~m+1)。对于很多涉及回路的题目,只要压成三个状态:0:没有插头,1:左插头,2:右插头。对于路径问题(虽然我还没写过),在以上基础上加“3:独立插头”来体现路径的特点(自行脑补)。

这样,很多题目就可以采用3进制(实际上是压2个Bit)来解决了,可以把涉及位运算的部分写成函数,这样编程复杂度大大下降。

 

BZOJ1814 Ural 1519 Formula 1

有坏点,求完全覆盖的哈密顿回路条数。

直接上。

 

BZOJ3125 CITY

有坏点,且有些点只能横向/纵向通过。

直接上。

 

BZOJ1210 [HNOI2004]邮递员

比第一题限制还少,没坏点,答案乘2,但需要高精(实测 long double 90 分)。

 

BZOJ1187 [HNOI2007]神奇游乐园

给定一张图,每个点有点权,求一个权值和最大的回路。

哈希表取max就好了。

 

BZOJ2331 [SCOI2011]地板

把每条线看成路径,0:无插头,1:有插头且伸出去的线可以再弯,2:有插头但伸出去的线不能弯。

之后就需要自己YY一下,把各种转移都搞出来。调试给我的经验是,对于分类讨论情况比较多的时候,不要为了让代码看起来感觉简洁而写的很“骚”,而应该是清晰地讨论每种情况。

转移情况就不写了,看看代码就能明白,实在不能理解的可以去zzh博客看。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974