RainAir
My OI Blog
RainAir
轮廓线 dp 学习笔记

轮廓线 dp 也是一种状压,适用于一维特别大而另一维特别小的情况。
我们来从一道经典例题入手:求 $1 \times 2$ 的骨牌填满 $n \times m $ 的矩形的方案数。
如果 $n,m \leq 11$ 那么当然可以轻松状压了,但是如果 $n = 10^5$ ,我们就要考虑使用轮廓线 dp 了。
设 $f_{i,S}$ 表示我们填到第 $i$ 行,我们在状压的状态中记录下图红线上的格子的状态。

https://blog.aor.sd.cn/wp-content/uploads/2019/08/QQ20190826-205135.png

(圆圈为现在要填的格子)
发现对于一个格子 我们只需要考虑这个格子上是放向上的骨牌,还是向左还是不放。如果上面是空格子那么必须要放向上的格子,否则向左和不放都可以。
考虑放了向上的格子后变成了什么:

https://blog.aor.sd.cn/wp-content/uploads/2019/08/QQ20190826-205206.png

发现只有填的那个位置变成了 $1$ 直接简单位运算操作一下就可以了。
其他状态可以尝试自己推一下,实在不懂了可以去看代码(

一个进阶小题

我们考虑如果可以使用 $1\times 1$ 和 $1\times 2$ 的块,并且限制 $1\times 1$ 的使用次数,限制某些块不能填,那么怎么做?(HDU 4804
也可以设 $f_{i,j,S}$ 表示第 $i$ 行用了 $j$ 个 $1\times 1$,轮廓线的状态。
只需要按照上面和定义转移就可以了,注意判断一下如果这个格子被限制不能填的话直接从上一个状态转移就可以了。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/786
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

轮廓线 dp 学习笔记
轮廓线 dp 也是一种状压,适用于一维特别大而另一维特别小的情况。 我们来从一道经典例题入手:求 $1 \times 2$ 的骨牌填满 $n \times m $ 的矩形的方案数。 如果 $n,m \leq 11$ 那么当然…
扫描二维码继续阅读
2019-08-26
标签
近期评论