SZ Horizon
SZ Horizon

『OI笔记』插头DP

前言

  好家伙,木板题都是黑题,这东西还要不要学了?(好吧还是要的。)

https://pro.goforit.top/stephen-zeng/img/master/202109091.png

正文

定义

插头

  首先,我们定义插头这个概念。如图:

https://pro.goforit.top/stephen-zeng/img/master/202109092.png

对于这个图,在格子[1,1]中,我们说这有一个下插头,在格子[2,1]中,我们说这里有一个上插头。

轮廓线

  如图:

https://pro.goforit.top/stephen-zeng/img/master/202109093.png

对于图中黄色格子[2,3],轮廓线就是这一条红色的线,而插头DP的一大精髓就是表示轮廓线的状态(这还可以理解把。 :mrgreen:

思路

  所以,插头DP的思路就是通过枚举m,n,记录下可以达到该轮廓线的状态的个数。

状态储存

  由于插头的特性,我们可以保证两两插头之间是可以互相匹配的(zhy神奔所说,如果不是找他麻烦),这样我们就可以用括号匹配的记录方法来记录状态。
  所以,我们可以定义:

  • “1”为左括号
  • “2”为右括号
  • “0”为没有括号

  举个粒子 :roll: ,如图:

https://pro.goforit.top/stephen-zeng/img/master/202109094.png

对于这三种状态,我们可以用这三串数字表示:

  • 1122012
  • 1120212
  • 1120002

  但是,由于有三种状态,我们就不能用二进制了。。。马?当然不是。如果你是神奔,你当然可以手写三进制。但是我们可以用两个二进制来表示4种状态,只不过有一种永远都永不上罢了。

To Be Continued…

Stephen Zeng

文章作者

发表回复

textsms
account_circle
email

SZ Horizon

『OI笔记』插头DP
前言   好家伙,木板题都是黑题,这东西还要不要学了?(好吧还是要的。) 正文 定义 插头   首先,我们定义插头这个概念。如图: 对于这个图,在格子[1,1]中,我们说这有一个下插…
扫描二维码继续阅读
2021-09-09