『OI笔记』插头DP

前言

好家伙，木板题都是黑题，这东西还要不要学了？（好吧还是要的。）

正文

¶定义

¶插头

首先，我们定义插头这个概念。如图： 对于这个图，在格子[1,1]中，我们说这有一个下插头，在格子[2,1]中，我们说这里有一个上插头。

¶轮廓线

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

¶思路

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

¶状态储存

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

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

举个粒子 :roll: ，如图： 对于这三种状态，我们可以用这三串数字表示：

• 1122012
• 1120212
• 1120002

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

To Be Continued…