「YLLOI-R1-T4」枫 的题解

· · 题解

看到题目后，很容易想出使用动态规划，那么我们试着用动态规划解决该题。

发现数据范围比较小，于是我们不妨大胆一些定义状态。发现动态规划可以逐行转移，因为确定了前若干行的状态后，便不需要再更改，只需要再考虑后面的，无后效性。那么第一个维度就显然可以使用行数。

因为列与列之间没有明显的区分度，所以我们只能使用节点数定义第二维度。只定义该行的节点数显然是不够的，因为该行每一个节点的父节点选择是之前行的所有节点，因此第二维度定义为当前总节点数。

那么定义 f_{i,j} 表示在 i 行 m 列的网格中，根节点在第一行且总节点数为 j 个的总方案数。

边界很显然，当只有一个根节点时一共有 m 种方案，即 f_{i,1}=m。

目标也很显然，所以情况相加即为答案：

\sum_{i=1}^n\sum_{j=1}^{n\times m}f_{i,j}

接下来我们看转移。

对于每一个 f_{i,j}，枚举第 i 行的节点数量相加即可。当该行有 k 个节点时，这 k 个节点有不同的位置选择，即从 m 个格子中选择 k 个，即 \binom{m}{k}，对于每个节点而言，其可以选择任意一个之前行的节点作为自己的父亲，因为共有 j-k 种选择，一共 k 个节点，一共就是 (j-k)^k 种选择。那么转移式即：

f_{i,j}=\sum_{k=0}^{m}f_{i-1,j-k}\times \binom{m}{k}\times (j-k)^k

组合数和乘方参数都比较小，因此可以直接预处理出来。那么总时间复杂度即 \mathcal O(n^2m^2)。

于是该题就写完了，不过有一些小细节以及一些小常数优化，这里就不再说明。