AGC041F Histogram Rooks

pufanyi

题解

发布于：Mar 19, 2020

有一个 $n\times n$ 的棋盘（$n\le 300$），然后对于每一列，考虑将所有该列纵坐标大于等于 $a_i$ 的格子全部删掉。在剩余期盼中，问有多少种放车的方案能使每个格子都能被至少一个车攻击到。

首先考虑到这样一件事情，就是如果用 $\left<l,r,h\right>$ 表示的是 $[l,r]$ 区间内，纵坐标大于 $h$ 的格子，我们定义一个这样的三元组为一个状态。

然后我们考虑对于每个状态，它里面的格子，如果要合法的话，每一列一定是下面三种中的其中一种：

1. 这一列中至少有一个车。这时候的话，这一列中的每个格子就一定合法。
2. 这一列没有车，但是这些格子都被一个车覆盖到了，也就是说这个二元组所包含的格子中没有。
3. 这一列没有车，而且部分格子并没有被车覆盖到，这时候，就这一列只能在 $h$ 下面有车才能合法。

现在我们考虑 dp，$f_{t,i,j}$ 表示状态为 $t$ 的时候，现在有 $i$ 个 $2$ 类点，$j$ 个 $3$ 类点，那么显然 $1$ 类点就是 $r-l+1-i-j$ 个。

然后我们考虑转移，我们考虑 $t$ 所表示的方格是否完全被分成了两块，也就是 $h$ 是否跟 $[l,r]$ 中最小的 $a$ 相等。如果是的话，那么我们就将其分成两半进行 dp，记左边那个状态为 $l(t)$，右边为 $r(t)$，那么我们可以得到转移 $f_{t,i,j+1}=\sum_{a,b}f_{l(t),a,b}\cdot f_{r(t),i-a,j-b}$，因为两块是不相干的。

然后我们如果没有，也就是说我们要从 $\left<l,r,h+1\right>$ 向 $\left<l,r,h\right>$ 转移。我们令$u=\left<l,r,h+1\right>$，$k,i,j$ 分别表示三类列的数量。这个转移需要分 $2$ 中情况讨论：

1. 如果这一行不放车：$f_{t,0,i+j}\leftarrow f_{u,i,j}$。
2. 如果这一行的车只放在一类列上：$f_{t,i,j}\leftarrow f_{u,i,j}\cdot (2^{k_1}-1)$。
3. 如果 $x$ 个车放在 $2$ 类列，$y$ 个车放在 $3$ 类列：$f_{t,i-x,j-y}\leftarrow f_{u,i,j}\cdot\binom{i}{x}\binom{j}{y}\cdot2^{k}$。

我们考虑优化这个 dp。

我们发现对于一个状态 $t$，有两种形式：

1. 每一行都至少有一辆车。
2. 有一行没有车。

为什么要把这两种分开来讨论呢？

我们考虑这两种有什么不一样。第一种形式，都有一个车，那么就没有第 $3$ 类列了，否则如果是第二种形式，那就最终就没有第 $2$ 类列了。这样子，其实我们就相当于分两种情况，把 $2$ 类列和 $3$ 类列看成是一个东西一起转移了，可以把她们放在同一维里，然后加一维 $0/1$ 即可。

这样第二种转移的时候，我们也只要枚举一维 $x$ 表示 $2,3$ 类列总的放车个数，考虑到复杂度为 $\sum \ell^2$，$\ell$ 表示的是每个有用状态的长度，不难发现复杂度为 $\mathcal{O}(n^3)$。

upd：啥听说这题 std 被艹了？算了先鸽着，丢个 链接，应该会补的（

更新于：Jul 2, 2023

DP

AtCoder