JOISC 2023 D1T2 题解

Un1quAIoid · 2023-07-02 23:36:49 · 题解

传送门： P9330

牛逼 dp。

step1 (n \le 8)：

首先真贪心是把区间按照右端点排序，然后从前到后能选就选。

我们考虑求答案的补，即计算假贪心能够求出正确答案的方案数，总方案数为 1-2n 中所有奇数之积，所以当 n \le 8 时直接 dfs 即可。

总方案数的证明考虑 i 从 1 至 n 安排 a_i,b_i:

• 当安排 a_i 时方案数为 1，只能安排最小的未被选过的数。
• 当安排 b_i 时方案数为 2n-2i+1，可以安排任意一个未被选过的数。

step2 (n \le 300)：

将真贪心选中的区间称为红区间，假贪心选中的区间称为蓝区间，注意两种贪心可能选中同一个区间，不妨将这种区间称为紫区间，其它区间则为黑区间。

那么一组红区间应当满足的性质为：

• 相邻两个红区间无交。
• 两个相邻红区间的右端点之间不存在其它完整区间，特别的，第一个红区间的右端点之前不存在其它完整区间。

同时也容易证明当一组区间满足上述条件时，这组区间也一定是真贪心选出来的红区间。

同样可以得出蓝区间的性质：

• 相邻两个蓝区间无交。
• 前一个蓝区间的右端点和后一个蓝区间的左端点之间不存在其它区间的左端点，特别的，第一个蓝区间的左端点之前不存在其他区间的左端点。

和红区间一样，满足上述性质的一组区间也一定是假贪心选出的蓝区间。

我们再将红蓝区间放到一起观察，由于要求红蓝区间个数相等，所以我们将第 i 个红区间与第 i 个蓝区间配对，可以发现第 i 个红区间的右端点一定大于第 i-1 个蓝区间的右端点，小于等于第 i 个蓝区间的右端点。

配合下图理解（截自日文题解）：

dp 的最重要一步来了：考虑按顺序每次插入一对红蓝区间。

具体来说，在 dp 状态中记录当前已经插入的区间个数 i，转移就考虑每次插入“一对新的红蓝区间以及所有右端点在当前最后一个红区间右端点和新插入的红区间右端点之间的黑区间”，所以我们需要枚举新插入的黑区间个数 j；同时我们还需要为这些新插入的黑区间右端点分配左端点，而左端点还有关于蓝区间的限制（见上文），所以还需要在状态中记录之前能插入一个左端点的位置数 k；同时还要添一维 0/1 表示当前这对红蓝区间是不是紫区间。

转移细节就不展开写了，不是重点。

于是我们就得到了状态 O(n^2)，转移 O(n) 的 O(n^3) dp。

step3 (n \le 3000)：

按照插入区间的思路，转移感觉上就是不可避免地需要枚举插入的黑区间个数，所以我们考虑优化状态数。

观察上述的 O(n^2) 状态的 dp，注意到需要多出来一维 k 是因为左端点有较强的限制，但是右端点的限制较弱，于是我们就可以考虑去转换左右端点。

具体来说，我们考虑倒着插入每一对红蓝区间，枚举新插入的黑区间数量 j，同时为新插入的黑区间左端点分配右端点，这时就会发现右端点是可以插入到之前任意两个端点之间的！

于是我们可以设计 dp：f_{i,0/1} 表示当前已经插入了 i 个区间，当前这对红蓝区间是(1)否(0)是紫区间，根据 0/1 不同一共有 4 种转移式，这里具体展开一下 0 \rightarrow 0 的转移式：

其中 (2i-2+(j-1))^{\underline{j}} 为插入 j 个黑区间右端点的方案数，(j+2)(j+1) 为将共计 j+3 个端点划分为 3 段的方案数，配合下两图理解：

其它 3 种转移大同小异，请自行画图理解。

于是我们得到了状态 O(n)，转移 O(n) 的 O(n^2) dp，同时也存在其它 O(n^2) dp 方法，但大多由于为状态 O(n^2)，转移 O(1) 而无法进一步优化。