插头DP

前言

今天学长讲了插头DP， 以前觉得他的模板就是黑题， 一定非常的难， 但是学习了之后发现它其实挺好理解， 但是难度该黑。

鉴于水品有限， 只简短的说一说， 给自己梳理一下思路。

算法

我们从模板题的弱化版开始讲：

P5074 Eat the Trees

我们发现要是闭合回路， 这只能老老实实状压， 不然没法让它合法， 更别说转移求方案数了， 但是这个线有很复杂， 可能可以压， 但是转移就需要巨复杂的分讨， 我们就不想了。 这时候就有两个巨牛的东西具有很好的性质， 可以很轻松的转移并且状态相对较少。

轮廓线和插头

就是我们维护这一排格子的轮廓线， 如图（from OI-wiki）：

我们将所有拐角往前推进， 然后枚举其所有状态， 我们在拐角处分讨推出下一个状态。

插头就是经过轮廓线的线， 也就是还没闭合的线， 就是支出来的线头， 可知我们轮廓线的每个位置只有两个状态， 这样子状态数就下来， 专一的话分讨也少了。

P5056 【模板】插头 DP

考虑只能有一个闭合回路， 所以我们的状态和转移就要保证只能有一个， 并且要只根据状态即可判断， 因为统计的是方案数， 我们的判定只能依据DP数组里面有的状态， 那我们可以考虑将插头定义为两种， 左插头和右插头， 只有在最后一个位置， 才能将左插头和右插头拼上， 那么分讨转移即可。

考虑为了方便我们用四进制来写， 三进制也可以， 但是四进制状态太多， 我们存不下， 可以拿个哈希表存储有用的状态， 也就是上一行推出的状态开个哈希表存起来， 这样子就是 \(O(3^12)\) 个状态。