轮廓线 dp 是一种和插头 dp 基本相同的东西,所以先看一下轮廓线 dp。 Tiling Dominoes# 与状压 dp 不同的是,轮廓线 dp 是通过逐格转移来进行 dp 的。我们用三维fi,j,kfi,j,k来表示 dp 状态。其中,i,ji,j表示当前进行到(i,j)(i,j)这个格子,kk表示轮廓线状态。具体的,在下面的情况中,k=(11001001)...
特别地,对于第三种,每次 insert 的时候都需要转化成最小表示法的形式(因为连通块之间是没有顺序的,所以可以多压一)。 然后是状态是转移方法,一般而言轮廓线 DP 每个阶段存在的合法状态不会特别多,所以可以考虑把合法状态哈希存储,然后在下一个阶段就只需要找出哈希表里所有的元素即可,发现这一部分是可以滚动的,进...
首先先想到状压每一行颜色,然后逐行转移,用四进制卡常一下。 复杂度是多少呢?我们转移一行需要暴力枚举上一行与当前行的状态。 相乘得到 O(n*4^(2m))。 掏出计算器算算,是 429496729600 左右,于是你皱了皱眉头(这能过就有鬼了 我们观察复杂度,发现瓶颈是枚举当前行状态,太浪费时间了,怎么办呢? 我们当然想要...
轮廓线 dp 也是一种状压,适用于一维特别大而另一维特别小的情况。 我们来从一道经典例题入手:求 的骨牌填满 的矩形的方案数。 如果 那么当然可以轻松状压了,但是如果 ,我们就要考虑使用轮廓线 dp 了。 设 表示我们填到第 行,我们在状压的状态中记录下图红线上的格子的状态。 (圆圈为现在要填的格子) 发现对于...
我们可以画出一条轮廓线,轮廓线的左下角(也可以是左上角、右上角、右下角)已经满足了条件,而另一边的点有待解决,这时候,我们通过一点点地改变轮廓线,就可以 DP 出想要求解的问题的最优值。相似的题目,还有2020 ICPC Shanghai 的 F,这题需要在 DP 前做若干推导和转化,有兴趣的读者可以阅读 walker shi:...
轮廓线dp,状压 在这道题中,假设我们有一个 5*5 的格子要填充(如图),黑色部分不是格子的一部分,只是作为虚拟出来的"顶"。 图1中蓝色部分表示已经填充好的部分;黄色部分是状态压缩表示的状态,已经填充为1,没有为0;红色表示当前处理的位置。 图2中我们用状态01111表示当前的"轮廓"。这个状态的"头"总是在"当...
dp[cur][0]); } return 0; } POJ2411 平面骨牌密铺,如果选用和插头dp类似的轮廓线转移方式做,状态转移会比较方便,因为状态转移到另一种状态的种类数有限。此次记录轮廓线下方(与上题不同,轮廓线上有段竖直的线状态不计)的方块是否已经被占用,进行状态转移。大体与上一题类似。#...
轮廓线dp 也是基于状压dp的一种。最经典的问题莫过于棋盘覆盖了,例如用1*2orL型骨牌覆盖N*M棋盘得方案个数。一般M不会太大。 例如这一道,由于形状特殊,轮廓线长度为M+1才可,递推时只要满足轮廓线前面的格子都是满的且当前放置方案合法即可。 有四种不同放置方法,...
POJ 1739 Tony's Tour (插头DP,轮廓线DP) 题意:给一个n*m的矩阵,其中#是障碍格子,其他则是必走的格子,问从左下角的格子走到右下角的格子有多少种方式。 思路: 注意有可能答案是0,就是障碍格子阻挡住了去路。 插头DP有两种比较常见的表示连通信息的方式:...
由于n和m都比较小,可以用轮廓线,就是维护最后边所需要的几个状态,然后进行DP。这里需要维护的状态数就是min(n,m)。即大概是一行的大小。每次放的时候,只考虑(1)以当前格子为右方,进行横放;(2)以当前格子为下方进行竖放;(3)还有就是可以不放。