首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

插头DP小结_dp插头接线标准

插头DP一般都是棋盘模型,找路径或者环路最值或者方案数。 插头:说白了就是两个联通的格子,一个走向另一个,那么这里就有一个插头。 轮廓线:DP逐格DP,那么轮廓线可以分开DP过的格子和未DP的格子。轮廓线的长度明显是m+1。插头垂直于轮廓线。 转移: 轮廓线在换行的时候要位移,这个画画图就出来了。 然后具体问题具体讨论。比如任意多个环路,不考虑方向,那么就是eat the trees,用最小表示法,因为是任意多个环路,那么插头只有两种,一种是有插头,一种是没插头,具体联通与否我们不管。如果要考虑方向呢?那么插头就有3种,一种是没插头,一种是插头从已DP的指向未DP的,一种是未DP的指向已DP的。 具体实现,有两种思路,一种是括号序列,一种是最小表示法。 括号序列比较快,空间压缩得很好,不过转移太麻烦辣。 最小表示法转移比较好想,就是比较慢,空间比较大。 写法有三种,一种是hash表存取状态,有decode,encode,就是kuangbin那种写法;一种是传统dp写法,位运算取出状态;还有种是claris写法,预处理所有可能状态然后传统DP转移。 kuangbin那个因为位运算比较少,每次都会直接接触到解密的状态,比较直观好想,模式化很强,不过每次都有O(m)的常数用在加密解密上。时空耗费较大,要写hash表,代码较长。 传统DP转移有的是O(1),有的O(n),总体来说和上面的差不多。。因为递推转移无效状态比较多。然后代码比较短。缺点就是一堆位运算像我这种傻逼根本看不懂 claris写法太神辣。因为所有状态预处理好了所以状态数很少,因为预处理所以所有转移O(1),然后代码很短。缺点是我这种傻逼不会预处理。然后还是一堆位运算。并且遇到题目本身状态很多的时候效果不会很好。 我现在只会第一种写法。 下面扔2个例题。 HYSBZ 3125 找一条走过所有格子的环路的方案数。 有的格子只能上下经过,有的只能左右经过,有的不能经过。 这个题我写的括号序列。 插头3种,空插头,左括号,右括号。 然后分9类情况讨论即可。 因为分了9类情况所以代码长爆。

03
领券