好家伙,木板题都是黑题,这东西还要不要学了?(好吧还是要的.)
首先,我们定义插头这个概念.如图:
对于这个图,在格子[11]中,我们说这有一个下插头,在格子[21]中,我们说这里有一个上插头.
对于图中黄色格子[23],轮廓线就是这一条红色的线,而插头DP的一大精髓就是表示轮廓线的状态(这还可以理解把.
由于插头的特性,我们可以保证两两插头之间是可以互相匹配的(zhy神奔所说,如果不是找他麻烦),这样我们就可以用括号匹配的记录方法来记录状态.
对于这三种状态,我们可以用这三串数字表示:
但是,由于有三种状态,我们就不能用二进制了.马?当然不是.如果你是神奔,你当然可以手写三进制.但是我们可以用两个二进制来表示4种状态,只不过有一种永远都永不上罢了.