SPOJ CAKE3. Delicious Cake

Vjudge | SPOJ | TG

先复习一下 插头 dp 大字典。本题显然使用染色模型。轮廓线上只有 m 个位置,而且不需要 roll() 操作(不过生成的新插头,要求前面的区分开来,所以我们还是用 m+1 来标记)。这样搞得话,2×2 我们会算出答案等于 14,仔细观察,是因为我们多算了下面两种不合法的情况。

我们发现这类情况都是因为在前面的转移中产生了刻痕,而使得后续的插头合并不合法,需要进一步编码。
我们可以给每个连通块强行上一个颜色,不相同的颜色不可合并。但是因为原问题没有颜色,这样计数起来会比较麻烦(需要最小染色,并且必须保证相同颜色的连通块必被合并)。
我们也可以暴力记录 C(5,2) 个连通块之间是否产生过刻痕,这样合并的时候直接判断即可。

刻痕的维护,首先每次状态转移,当前插头都需要和相邻两个插头(左插头和上插头)都标记刻痕。
其次,因为我们使用了最小表示,连通块的记号会被 relable,因而编码的时候也需要重新映射。
最后插头合并的时候,刻痕信息也需要合并。

最后上一下高精度模板就好了。留个 OEIS 地址方便大家 debug。