首页 > 笔记 > 插头DP——从不会到崩溃

插头DP——从不会到崩溃

插头DP,按我的理解,就是一种非常特殊的恶心转移状压DP。

插头DP有下面的分类:

  • 按模型:多回路问题、单回路问题、简单路径问题、广义路径问题
  • 按表示方法:是否有插头、括号法(广义括号法)、最小表示法

插头DP最朴素的实现就是用f[i][j][k]记下在(i, j)这个点轮廓线状态为k的答案。


接下来就具体讲一下插头DP

究竟什么是插头呢

一个格子某个方向的插头存在表示这个格子在这个方向与相邻格子相连。

什么是轮廓线呢

已决策格子和未决策格子的分界线

插头DP解决的一类问题是

棋盘模型
所有的非障碍格子连通

其实基础的就是各种棋盘回路问题

考虑如何遍历所有的点

  • 逐行递推
  • 逐个递推

逐行递推

不妨按照从上到下的顺序依次考虑每一行.分析第i 行的哪些信息对第i + 1行有影响:我们需要记录第i行的每个格子是否有下插头,这决定了第i+1行的每个格子是否有上插头.仅仅记录插头是否存在是不够的,可能导致出现多个回路。对于要求回路数量的题目来说,我们需要记录插头的连通性。

 

images

通过上面的分析,可以写出动态规划的状态:images 表示前i行,第i行的n个格子是否具有下插头的一个n位的二进制数为S0,第i行的n个格子之间的连通性为S1的方案总数.
如何表示n个格子的连通性呢? 一般会使用最小表示法:
一种最小表示法为:所有的障碍格子标记为0,第一个非障碍格子以及与它连通的所有格子标记为1,然后再找第一个未标记的非障碍格子以及与它连通的格子标记为2,……,重复这个过程,直到所有的格子都标记完毕.如上图三个状态我们可以依次表示为:

images

状态表示的优化:

通过观察可以发现如果轮廓线上方的n个格子中某个格子没有下插头,那么它就不会再与轮廓线以下的格子直接相连,它的连通性对轮廓线以下的格子不会再有影响,也就成为了“冗余”信息.不妨将记录格子的连通性改成记录插头的连通性,如果这个插头存在,那么就标记这个插头对应的格子的连通标号,如果这个插头不存在,那么标记为0.这样状态就从精简为,上图三个状态表示为:

images

优化后不仅状态表示更加简单,而且状态总数将会大大减少.

逐格递推

按照从上到下,从左到右的顺序依次考虑每一格.分析转移完(i, j)这个格子后哪些信息对后面的决策有影响:同样我们可以刻画出轮廓线,即轮廓线上方是已决策格子,下方是未决策格子.由图可知与轮廓线直接相连的格子有n个,直接相连的插头有n+1个,包括n个格子的下插头以及(i, j)的右插头.为了保持轮廓线的“连贯性”,不妨从左到右依次给n个格子标号,n+1个插头标号.类似地,我们需要记录与轮廓线直接相连的n+1个插头是否存在以及n个格子的连通情况.

通过上面的分析,很容易写出动态规划的状态:

images

表示当前转移完(i, j)这个格子,n+1个插头是否存在表示成一个n+1位的二进制数S0,以及n个格子的连通性为S1的方案总数.

images

逐行递推的时候我们提到了状态的优化,同样地,我们也可以把格子的连通性记录在插头上,新的状态为images,上图3个状态依次为

images

我们进一步分析一下

对于轮廓线上的每一条交点,都是一条回路的一端

images

我们进一步看到话,可以得到一个很神的性质

【性质】轮廓线上从左到右4个插头a, b, c, d,如果a, c连通,并且与b不连通,那么b, d一定不连通.

证明:反证法,如果a, c连通,b, d连通,那么轮廓线上方一定至少存在一条a到c的路径和一条b到d的路径.如图,两条路径一定会有交点,不妨设两条路径相交于格子P,那么P既与a, c连通,又与b, d连通,可以推出a, c与b, d连通,矛盾,得证.

images

这个性质对所有的棋盘模型的问题都适用.

因为这种神奇的性质,我们可以用括号序列来表示插头

images

images

但是这种DP该如何转移呢。

这里分三种情况,

  1. 新建一个连通分量
  2. 合并两个连通分量
  3. 保持原来的连通分量

例1

1519. Формула 1
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Вступление
Несмотря на то, что Вологда не добилась права проведения Олимпийских Игр 20** года, как всем уже стало известно, она будет принимать один из этапов Гран-при Формулы 1. Конечно, для такого ответственного мероприятия надо построить новую трассу, а также гостиницы, рестораны, международный аэропорт и всё остальное, что может понадобиться болельщикам, которые вскоре наводнят Вологду. Но когда все гостиницы и половина ресторанов были уже построены, выяснилось, что на месте будущей гоночной трассы помимо рабочих в вагончиках живут ещё и суслики в норках. Так как мы все любим животных, экологи ни за что не позволят укладывать трассу поверх нор. И вот теперь мэр сидит в своём кабинете, грустно склонившись над картой будущей трассы, на которую нанесены обиталища ненавистных сусликов.
Задача
Кто же сможет нарисовать план трассы и тем самым спасти город от неминуемого позора? Мэру помогут лишь настоящие профессионалы своего дела, закалённые в боях программисты из местного технического вуза! Весь город устремил свои взоры на первую команду политеха. Но так как наши герои не ищут лёгких путей, они решили поставить себе гораздо более сложную задачу: «Наверняка мэр очень обрадуется, если мы найдём, сколько всего трасс можно построить на данном участке!»
Надо сказать, что трасса в Вологде будет устроена довольно просто. Это прямоугольник размерами N*M, через каждую клетку которого проходит ровно один участок трассы. Дорога всегда должна идти параллельно одной из сторон исходного прямоугольника, так что повороты возможны лишь под прямым углом. На рисунке ниже приведены два примера при N = M = 4 (серые квадраты – норы сусликов, жирная чёрная линия – трасса). Других способов построить трассу при таком расположении нор нет.
Problem illustration
Исходные данные
Первая строка содержит целые числа N и M (2 ≤ N, M ≤ 12). Каждая из следующих N строк содержит M символов – соответствующие клетки прямоугольника. Символ «.» (точка) обозначает клетку, через которую нужно проложить трассу, а символ «*» (звёздочка) – клетку, где находится норка суслика. Гарантируется, что есть хотя бы 4 клетки, через которые можно проложить трассу.
Результат
Вывести искомое количество способов. Гарантируется, что оно не превышает 263-1.
Примеры
исходные данные результат
4 4
**..
....
....
....
2
4 4
....
....
....
....
6

明确了题意我们就可以上代码了:

images


以上内容为作者被某人坑到爆炸为了报复社会而作的。没有任何的逻辑性,不适宜观看。

建议忘掉上文所有的东西,从下文开始看。

 

首先考虑一道例题

给你一个一个 m * n 的棋盘有的格子存在障碍求经过所有非障碍格子的哈密顿回路个数

m, n≤12

这个数据范围,一眼就是大爆搜或者状压啊。但是如果要爆搜的话,是\(O( (m \times n) !)\)的效率啊,肯定是过不了的。

那么,我们就要考虑状压DP!

先引入这样两个概念

何为插头

一个格子某个方向的插头存在表示这个格子在这个方向与相邻格子相连.对于一个4连通的问题来说,它通常有上下左右4个插头,本题要求回路的个数,观察可以发现所有的非障碍格子一定是从一个格子进来,另一个格子出去,即4个插头恰好有2个插头存在,共6种情况.

images

何为轮廓线

考虑递推的时候,肯定有的格子已经DP过了,有的格子还没有DP过。那么这么两块的分界线就是轮廓线。

至于棋盘里状态的递推,有两种,一种是逐行,一种是逐格。对于这题,逐格可以省掉逐行里的很多无用状态,所以,下面说的是逐格。

逐格的轮廓线就是这样的了:

images

DP的两个重要的点就是状态的表示和转移。

那么该如何优雅的表示状态呢?

我们考虑每一条轮廓线,它最多有\(n+1\)个插头穿过它。其中有\(n\)个下插头,\(1\)个右插头。而且轮廓线以上由若干条互不相交的路径构成,每条路径的两端对应两个插头。由于性质插头不会交叉,插头两两匹配

【性质】轮廓线上从左到右4个插头a, b, c, d,如果a, c连通,并且与b不连通,那么b, d一定不连通.

证明:反证法,如果a, c连通,b, d连通,那么轮廓线上方一定至少存在一条ac的路径和一条bd的路径.如图,两条路径一定会有交点,不妨设两条路径相交于格子P,那么P既与a, c连通,又与b, d连通,可以推出a, cb, d连通,矛盾,得证.

images

这就让我们想到了:括号序列!

0:无插头状态,用 # 表示
1:左括号插头,用 ( 表示
2:右括号插头,用 ) 表示

images

虽然3进制就够了,但是\(2^k\)进制因为是位运算,比较快,就用四进制了。

接下来我们来考虑一下状态的转移

对于每一个格子,我们可以研究一下它的状态和转移到的格子

images

可以看出这就相当于轮廓线上当前决策格子的左插头改成下一个的下插头,上插头改成下一个的右插头的状态.

我们在考虑一下插头在数组中的下标

上图中就是

下、下、左、上、上

变成了

下、下、下、右、上

所以用数组表示\(f[i][j][S]->f[i][j+1][S]\)的时候,S表示四进制的插头状态。考虑状态的表示的话,S原来第j位的就是那个右插头,j+1就是那个上插头。转移到下一个格子后,原来的j就变成了j格子的下插头,j+1就变成了j的右插头。

如何转移?

这里分三种情况,

  1. 新建一个连通分量
  2. 合并两个连通分量
  3. 保持原来的连通分量

第一种情况

新建一个联通分量

把\(j,j+1\)变为左括号和右括号

images

这时需要判断方格(i,j+1)和方格(i+1,j)是否还可以覆盖线段,以免生出无用状态。

是\(O(1)\)的。

第二种情况

合并两个连通分量

1、\(j\)为左括号,\(j+1\)为左括号。\(j,j+1\)改为无括号,\(j\)对应的右括号变为左括号。这个操作需要扫描整个括号序列,是\(O(n)\)的。

images

2、\(j\)为右括号,\(j+1\)为右括号。\(j,j+1\)改为无括号,\(j+1\)对应的左括号变为右括号,同上,是\(O(n)\)的。

images

3、\(j\)为右括号,\(j+1\)为左括号。\(j,j+1\)改为无括号,是\(O(1)\)的

images

4、\(j\)为左括号,\(j+1\)为右括号。这种情况值适用于最后的格子。\(j,j+1\)改为无括号,是\(O(1)\)的

images保持原来的连通分量

1、判断方格(i+1,j)是否可以覆盖线段。

images

2、判断方格(i,j+1)是否可以覆盖线段。

images

3、判断方格(i,j+1)是否可以覆盖线段。

images

4、判断方格(i+1,j)是否可以覆盖线段。

images

现在我们就已经讲完了所有转移。下面就是具体的实现了。

首先最大的问题就是状态的储存问题。我们的括号表示3进制就够了,但是4进制非常的和善(比较快。

因为m比较小,我们可以直接把状态直接压成一个int,一个四进制的数需要两个二进制位来储存。我们该如何提取呢,在开始的时候,我们可以预处理一个bit数组

它的结果是

\[bit[]={0,2,4,6,8,10,12 \dots }\]

这样的话,我们每次需要提取第i位的话,我们就可以直接把S右移\(bit[i]\)位再与4取模。因为和4取模的话就是留下两位。(建议用计算器试试)

假如要添加状态就可以直接加上就可以了。

还有一个细节就是每次更新的时候需要hash一下,因为这个状态可能已经有过了,方案数是累加的。

hash表大概是这样的

images

内部实现是一个前向星伪链表。。

题目地址

代码

(建议这道题对着板子打一遍,插头DP其实是有规律的,敲过一次就熟练多了。

这一道题是上面题的改版

地址:poj1739

Tony's Tour
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 4152 Accepted: 1941
Description

A square township has been divided up into n*m(n rows and m columns) square plots (1<=N,M<=8),some of them are blocked, others are unblocked. The Farm is located in the lower left plot and the Market is located in the lower right plot. Tony takes her tour of the township going from Farm to Market by walking through every unblocked plot exactly once.
Write a program that will count how many unique tours Betsy can take in going from Farm to Market.
Input

The input contains several test cases. The first line of each test case contain two integer numbers n,m, denoting the number of rows and columns of the farm. The following n lines each contains m characters, describe the farm. A '#' means a blocked square, a '.' means a unblocked square.
The last test case is followed by two zeros.
Output

For each test case output the answer on a single line.
Sample Input

2 2
..
..
2 3
#..
...
3 4
....
....
....
0 0
Sample Output

1
1
4

在方格最后添加

.########.

..................

使得原问题转化为回路问题,即【URAL 1519】

为什么不能只添加一行...............呢?

这样可能会使得答案增加!可以蛇形走!

 

下一个问题是多回路问题

这类问题是最水的,只要记录当前位置有没有插头即可。比如说hdu1693

  • 有上插头和左插头 → 没有右插头或下插头
  • 没有上插头或做插头 → 有右插头和下插头
  • 只有一个插头 → 右插头和下插头分别只有一个

我们看一下题目

Problem Description
Most of us know that in the game called DotA(Defense of the Ancient), Pudge is a strong hero in the first period of the game. When the game goes to end however, Pudge is not a strong hero any more.
So Pudge’s teammates give him a new assignment—Eat the Trees!

The trees are in a rectangle N * M cells in size and each of the cells either has exactly one tree or has nothing at all. And what Pudge needs to do is to eat all trees that are in the cells.
There are several rules Pudge must follow:
I. Pudge must eat the trees by choosing a circuit and he then will eat all trees that are in the chosen circuit.
II. The cell that does not contain a tree is unreachable, e.g. each of the cells that is through the circuit which Pudge chooses must contain a tree and when the circuit is chosen, the trees which are in the cells on the circuit will disappear.
III. Pudge may choose one or more circuits to eat the trees.

Now Pudge has a question, how many ways are there to eat the trees?
At the picture below three samples are given for N = 6 and M = 3(gray square means no trees in the cell, and the bold black line means the chosen circuit(s))

images

Input
The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 10 cases.
For each case, the first line contains the integer numbers N and M, 1<=N, M<=11. Each of the next N lines contains M numbers (either 0 or 1) separated by a space. Number 0 means a cell which has no trees and number 1 means a cell that has exactly one tree.

Output
For each case, you should print the desired number of ways in one line. It is guaranteed, that it does not exceed 263 – 1. Use the format in the sample.

 

Sample Input
2
6 3
1 1 1
1 0 1
1 1 1
1 1 1
1 0 1
1 1 1
2 4
1 1 1 1
1 1 1 1

Sample Output
Case 1: There are 3 ways to eat the trees.
Case 2: There are 2 ways to eat the trees.

这个用回路来覆盖就可以了,没有限制数量。

非常的水啊【相比来说

题目描述

经历了一段艰辛的旅程后,主人公小P乘坐飞艇返回。在返回的途中,小P发现在漫无边际的沙漠中,有一块狭长的绿地特别显眼。往下仔细一看,才发现这是一个游乐场,专为旅途中疲惫的人设计。

娱乐场可以看成是一块大小为n*m的区域,且这个n*m的区域被分成n*m个小格子,每个小格子中就有一个娱乐项目。然而,小P并不喜欢其中的所有娱乐项目,于是,他给每个项目一个满意度。满意度为正时表示小P喜欢这个项目,值越大表示越喜欢。为负时表示他不喜欢,这个负数的绝对值越大表示他越不喜欢。为0时表示他对这个项目没有喜恶。

小P决定将飞艇停在某个小格中,然后每步他可以移动到相邻的上下左右四个格子的某个格子中。小P希望找一条路径,从飞艇所在格出发,最后又回到这个格子。

小P有一个习惯,从不喜欢浪费时间。因此,他希望经过每个格子都是有意义的:他到一个地方后,就一定要感受以下那里的惊险和刺激,不管自己是不是喜欢那里的娱乐项目。而且,除了飞艇所在格,其他的格子他不愿意经过两次。小P希望自己至少要经过四个格子。

在满足这些条件的情况下,小P希望自己玩过的娱乐项目的满意度之和最高。你能帮他找到这个最高的满意度之和吗?

输入输出格式

输入格式:

输入文件中的第一行为两个正整数n和m,表示游乐场的大小为n&times;m。因为这个娱乐场很狭窄,所以n和m满足:2<=n<=100,2<=m<=6。接下来的n行,每行有m个整数,第i行第j列表示游乐场的第i行第j列的小格子中的娱乐项目的满意度,这个满意度的范围是[-1000,1000]。同一行的两个整数之间用空格隔开。

输出格式:

输出文件中仅一行为一个整数,表示最高的满意度之和。

输入输出样例

输入样例#1:

输出样例#1:

说明

大家测下这个数据 5 5 1 1 -100 3 3 1 1 -100 3 3 1 1 -100 3 3 1 1 -100 3 3 1 1 -100 3 3 结果是30?

地址luogu3190

转移和模版一样。

出解的情况就是当前格子的插头为(),且整个轮廓线上没有别的插头。(因为如果别的地方还有插头的话,必然会在后面几行中出现()插头的情况,就会多算了)

 


6 COMMENTS

  1. NIetzsche2017-03-24 下午9:27

    可爱的代码风格(对,我说的就是第一个代码)

  2. lch3162018-05-02 下午6:41

    良心讲解。我已经“崩溃”了。

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×