Stephen Horizon
Stephen Horizon

『OI笔记』插头DP

前言

表情包测试
:mrgreen: :neutral: :twisted: :arrow: :shock: :smile: :???: :cool: :evil: :grin: :idea: :oops: :razz: :roll: :wink: :cry: :eek: :lol: :mad: :sad: :!: :?:
  好家伙,木板题都是黑题,这东西还要不要学了?(好吧还是要的。)

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

Stephen Horizon

『OI笔记』插头DP
前言 表情包测试 :mrgreen: :neutral: :twisted: :arrow: :shock: :smile: :???: :cool: :evil: :grin: :idea: :oops: :razz: :roll: :wink: :cry: :eek: :lol: :mad…
扫描二维码继续阅读
2021-09-09