P9084 [PA 2018] Skwarki 对于题解的一些补充

· · 题解

还不会这个题的可以先看其他题解，这里补充一些点。

有可能因为我是蠢猪，但是希望能通过一下，因为有可能有人和我一样蠢 /kel。

下面使用的定义是把 i 个点全部删空。

不知道是不是我蠢了，反正我做这个题的时候思考了很久为啥 f_{i,j,1} 没有一个 2 的转移系数表示的是他的含有边界的子树是左子树还是右子树。

实际上是不用的，因为我们可以考虑说一个边界如果第一次作为了左子树，那么后面也一定作为左子树，如果第一次是右子树那么后面也一定作为右子树，因为边界只有可能是 1/n。

如果还是不理解，可以考虑我们将 dp 变得复杂一点，考虑变为 f_{i,j,0/1,0/1} 最后一个 0/1 表示的是他的边界是 1 还是 n，转移就变成了：

f_{i,j,1,0}=f_{k,t,1,0}\times f_{i-k-1,t',0,0} f_{i,j,1,1}=f_{k,t,1,1}\times f_{i-k-1,t',0,0}

（省略了一些系数）

然后你发现是可以把最后一维省去的，因为整个转移式子完全是对称的。