Battle of the Brains
【专辑】插头DP
欢迎大家移步去看这篇写的更详细的文章
先献上陈丹琦的大作http://www.docin.com/p-46797997.html
最近学习了这个与Dancing Links一样优美的插头DP (私以为这个算法将成为和去年的Dancing Links一样的热门算法)
从简单回路(2进制)，哈密顿回路(3进制)，再到简单路径(4进制)，广义路径(5进制)，每深入一层研究，就对这个算法有着更深刻的理解与着迷
同以往一样专题，下边分析几道题目:
多条回路
Eat the Trees
可以说是最最入门的插头DP题目,只要求用回路把所有格子全部走遍,所以都不用分左插头右插头,能合并就合并
哈密顿回路
Formula 1
论文上的入门题,求有多少回路,论文已经介绍了很详细,这里不再解释
由于是模板题,自然要大大的优化下,交了N遍,效率终于排到了rank1
Tony’s Tour
楼教主的男人八题,同上,论文上有构成回路的方法,解法与上题一模一样
Pipes
这题加上了权值,转移的时候很简单,DP处只要换成加权值以及比较大小就OK啦
Tour in the Castle
M很大,要很敏感的联想到矩阵,每列之间的转移建出方程,然后建矩阵求解,此题预处理只花了40MS,大部分时间用在矩阵上
下边是对于每个N所构成的K阶矩阵
2.2
3.4
4.7
5.20
6.33
7.114
Plan
HDOJ月赛刚刚出的题，我也正是因为比赛钱要测试这题才去学了这个算法
此题构图和教主那题差不多，差别是不要走过所有的格子，所以可以让有些格子没有插头
简单路径
Manhattan Wiring
找两条不相交的路,由于是要找最小的路,所以一些成环的一定是多余的路径,一定会被更新掉,所以就不必分左插头右插头,并且独立插头的位子都已经标好了,所以只要用3进制来表示是2的插头还是3的插头就OK了
Beautiful Meadow
cpg的神题,我能找到唯一一道简单路径的题,用论文中4进制表示的方法就能过,不过数据不是很强,我一开始错误的程序都过了
AC的同学请再试试下边这组数据
2 7
1 1 1 0 1 1 1
1 0 1 0 1 0 1
答案是5,我错误的程序跑出来是8
广义路径(由于用到5进制,四种插头,多了个中间插头,所以要分25种情况讨论,省赛迫在眉睫,暂时没时间搞这个了,等以后有空再来填这个大坑…..虽然用最小表示法的话可以较为简单的表示,但是效率不够高)
生成树计数http://www.box.net/shared/k5pp5ixc84
Delicious Cake http://www.acm.cs.ecnu.edu.cn/problem.php?problemid=1739
Black and Whit
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1513
Rocket Mania http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2125
Rocket Mania Plus http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2126
Maze Statistics
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1472
2010Harbin finals E Channel http://acmicpc-live-archive.uva.es/nuevoportal/
还是等完成了上边这个大坑后再献上全部模板….
Popularity: 23% [?]
准备学习插头DP= =先拜一下小HH，吸点RP…
[回复]
shǎ崽 回复:
十月 8th, 2011 at 22:28
回拜,区域赛RP++
[回复]
orz神牛……
对于eat the trees这道题，您是怎么用二进制解决的呢？
[回复]
[...] 以前写过一篇关于插头DP的文章 只浅浅的研究了最最基础的几个类型:多条回路,一条回路,简单路径 当时局限于括号表示法,死活无法继续研究更深层次的:广义路径 后来厚着脸皮问陈丹琦要了uva Black and White的代码,研读数遍之后”大彻大悟”,脱离了括号表示法,用最小表示法效率同样很高,并且操作非常方便.即便是最最复杂的情况用最小表示法也可以方便的表示 先来补充一下上篇文章介绍的简单的几个插头: [...]
弱弱的问下Tour in the Castle 您的矩阵快速幂是怎么实现的。。我一直TLE。。
[回复]
弱弱的问下，每次转移(譬如最简单的回路问题)有效状态数应该如何估计的？
[回复]
Orz…正在学这个，这么好的资料，得仔细研究下，嘿嘿~~
[回复]
shǎ崽 回复:
一月 31st, 2011 at 14:20
呵呵，过誉了，这资料不完全，后边的都还没整理出来呢。。。
[回复]
Dumbear 回复:
一月 31st, 2011 at 23:31
发现我写出来的跑得很慢啊……不知道是不是因为我把状态直接丢map的原因……
[回复]
问您一下Formula 1那题如果用普通的八进制最小表示法，应该跑多长时间呢？
[回复]
huyuealex 回复:
一月 20th, 2011 at 15:12
还有一个问题，如果是括号匹配的方法，“预处理每个状态每个括号所匹配的括号”是说在递推开始前就预处理好呢，还是在递推过程中对每个状态记录一下？
[回复]
shǎ崽 回复:
一月 21st, 2011 at 20:22
恩,其实我想再写一篇文章”插头DP完全版”的.可惜最近一直没时间写,这几天我争取抽空整理一下发出来~
谢谢到时候关注
[回复]
在做您列出的哈密顿回路的第一第二道题目的时候，觉得第一题Ural1519的模板难以套用到楼教主那题，主要是判断那里貌似改动较大，请问大牛您怎么解决模板适用性的。
[回复]
shǎ崽 回复:
九月 3rd, 2010 at 17:02
教主那题在最外围加上墙就好了~
xoo
ooo
变成
oooooo
oxxxxxo
oxxooxo
ooooooo
这样做虽然会增加点复杂度,但是很方便
或者判断下在最左下角的时候加一个右插头,还是比较好解决的
[回复]
BBTiger 回复:
九月 3rd, 2010 at 17:55
好办法，怪不得你归在3进制里面
[回复]
昵称(必须) 回复:
十一月 4th, 2010 at 20:08
其实地图可以不做任何改动，直接在最后面询问状态时找一个状态为10…02的dp值就行了
[回复]
shǎ崽 回复:
九月 3rd, 2010 at 17:05
哈密顿回路 和 简单路径 的模板基本不用改的
(主要是现在出现的题目都比较基础,如果再加一些限制条件的话就要改的面目全非了)
广义路径倒是几乎每道题的限制条件都不一样,模板出入很大.(前些时间做了还没来得及整理出来)
[回复]
hh，Formula 1你是用括号表示状态的么？如果是，求代码看看，为什么你这么快。谢谢！
[回复]
shǎ崽 回复:
八月 13th, 2010 at 13:20
是的,所有代码都是用括号匹配来写的,所以对于最后5进制的括号匹配我很纠结~
[回复]
Ascorpior 回复:
八月 14th, 2010 at 10:16
弱问，可以把Formula 1的代码发我邮箱不？
[回复]
shǎ崽 回复:
八月 14th, 2010 at 11:57
不要发代码么～我们谈思路吧～
[回复]
Ascorpior 回复:
八月 14th, 2010 at 17:46
哦，没事，我也过了，但是比较慢。。不晓得你括号写的怎么这么飘逸
[回复]
shǎ崽 回复:
八月 14th, 2010 at 18:35
括号用4进制表示，虽然只用到三个进制，但可以用四进制位运算加速优化～
还有，无效状态我不会遍历的，自己建两个表滚动加速
[回复]
插头dp？貌似很久以前就开始流传了……
不像dlx好像是去年刚兴起的
[回复]
这个要顶一下。抽空拜读~
[回复]
膜拜hh，祝hh省赛捧杯。。
[回复]
NB，YM
[回复]
狂顶300下~~~
[回复]
shǎ崽 回复:
四月 6th, 2010 at 19:40
[回复]