有一个 \(n\times n\) 的棋盘（\(n\le 300\)），然后对于每一列，考虑将所有该列纵坐标大于等于 \(a_i\) 的格子全部删掉。在剩余期盼中，问有多少种放车的方案能使每个格子都能被至少一个车攻击到。
首先考虑到这样一件事情，就是如果用 \(\left<l,r,h\right>\) 表示的是 \([l,r]\) 区间内，纵坐标大于 \(h\) 的格子，我们定义一个这样的三元组为一个状态。
然后我们考虑对于每个状态，它里面的格子，如果要合法的话，每一列一定是下面三种中的其中一种：
- 这一列中至少有一个车。这时候的话，这一列中的每个格子就一定合法。
- 这一列没有车，但是这些格子都被一个车覆盖到了，也就是说这个二元组所包含的格子中没有。
- 这一列没有车，而且部分格子并没有被车覆盖到，这时候，就这一列只能在 \(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\) 中情况讨论：
- 如果这一行不放车：\(f_{t,0,i+j}\leftarrow f_{u,i,j}\)。
- 如果这一行的车只放在一类列上：\(f_{t,i,j}\leftarrow f_{u,i,j}\cdot (2^{k_1}-1)\)。
- 如果 \(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\)，有两种形式：
- 每一行都至少有一辆车。
- 有一行没有车。
为什么要把这两种分开来讨论呢？
我们考虑这两种有什么不一样。第一种形式，都有一个车，那么就没有第 \(3\) 类列了，否则如果是第二种形式，那就最终就没有第 \(2\) 类列了。这样子，其实我们就相当于分两种情况，把 \(2\) 类列和 \(3\) 类列看成是一个东西一起转移了，可以把她们放在同一维里，然后加一维 \(0/1\) 即可。
这样第二种转移的时候，我们也只要枚举一维 \(x\) 表示 \(2,3\) 类列总的放车个数，考虑到复杂度为 \(\sum \ell^2\)，\(\ell\) 表示的是每个有用状态的长度，不难发现复杂度为 \(\mathcal{O}(n^3)\)。
upd：啥听说这题 std 被艹了？算了先鸽着，丢个链接，应该会补的（