有一个 𝑛×𝑛 的棋盘（𝑛≤300），然后对于每一列，考虑将所有该列纵坐标大于等于 𝑎𝑖 的格子全部删掉。在剩余期盼中，问有多少种放车的方案能使每个格子都能被至少一个车攻击到。
首先考虑到这样一件事情，就是如果用 ⟨𝑙,𝑟,ℎ⟩ 表示的是 [𝑙,𝑟] 区间内，纵坐标大于 ℎ 的格子，我们定义一个这样的三元组为一个状态。
然后我们考虑对于每个状态，它里面的格子，如果要合法的话，每一列一定是下面三种中的其中一种：
- 这一列中至少有一个车。这时候的话，这一列中的每个格子就一定合法。
- 这一列没有车，但是这些格子都被一个车覆盖到了，也就是说这个二元组所包含的格子中没有。
- 这一列没有车，而且部分格子并没有被车覆盖到，这时候，就这一列只能在 ℎ 下面有车才能合法。
现在我们考虑 dp，𝑓𝑡,𝑖,𝑗 表示状态为 𝑡 的时候，现在有 𝑖 个 2 类点，𝑗 个 3 类点，那么显然 1 类点就是 𝑟−𝑙+1−𝑖−𝑗 个。
然后我们考虑转移，我们考虑 𝑡 所表示的方格是否完全被分成了两块，也就是 ℎ 是否跟 [𝑙,𝑟] 中最小的 𝑎 相等。如果是的话，那么我们就将其分成两半进行 dp，记左边那个状态为 𝑙(𝑡)，右边为 𝑟(𝑡)，那么我们可以得到转移 𝑓𝑡,𝑖,𝑗+1=∑𝑎,𝑏𝑓𝑙(𝑡),𝑎,𝑏⋅𝑓𝑟(𝑡),𝑖−𝑎,𝑗−𝑏，因为两块是不相干的。
然后我们如果没有，也就是说我们要从 ⟨𝑙,𝑟,ℎ+1⟩ 向 ⟨𝑙,𝑟,ℎ⟩ 转移。我们令 𝑢=⟨𝑙,𝑟,ℎ+1⟩，𝑘,𝑖,𝑗 分别表示三类列的数量。这个转移需要分 2 中情况讨论：
- 如果这一行不放车：𝑓𝑡,0,𝑖+𝑗←𝑓𝑢,𝑖,𝑗。
- 如果这一行的车只放在一类列上：𝑓𝑡,𝑖,𝑗←𝑓𝑢,𝑖,𝑗⋅(2𝑘1−1)。
- 如果 𝑥 个车放在 2 类列，𝑦 个车放在 3 类列：𝑓𝑡,𝑖−𝑥,𝑗−𝑦←𝑓𝑢,𝑖,𝑗⋅(𝑖𝑥)(𝑗𝑦)⋅2𝑘。
我们考虑优化这个 dp。
我们发现对于一个状态 𝑡，有两种形式：
- 每一行都至少有一辆车。
- 有一行没有车。
为什么要把这两种分开来讨论呢？
我们考虑这两种有什么不一样。第一种形式，都有一个车，那么就没有第 3 类列了，否则如果是第二种形式，那就最终就没有第 2 类列了。这样子，其实我们就相当于分两种情况，把 2 类列和 3 类列看成是一个东西一起转移了，可以把她们放在同一维里，然后加一维 0/1 即可。
这样第二种转移的时候，我们也只要枚举一维 𝑥 表示 2,3 类列总的放车个数，考虑到复杂度为 ∑ℓ2，ℓ 表示的是每个有用状态的长度，不难发现复杂度为 O(𝑛3)。
upd：啥听说这题 std 被艹了？算了先鸽着，丢个链接，应该会补的（