题解

思路

分别记两行及两行之和的前缀和为 $S_1,S_2,S_0$。对 $k\in\{0,1,2\}$，令 $p_k(i)$ 为满足下列条件的最大左端点 $l$：存在 $r\le i$ 使 $S_k(l)=S_k(r)$。若不存在则为 $-1$。它表示在对应行集合的前 $i$ 列中，右侧最靠后的零和区间从哪里开始。

设 $F(x,y)$ 为只允许使用第一行前 $x$ 列和第二行前 $y$ 列时的最优答案。考虑最右侧被选中的矩形：

• 若它只占一行，贪心选择左端点更靠右的那一行不会变差；
• 若它占两行，其右端点不能超过 $\min(x,y)$，最靠右的可选左端点为 $p_0(\min(x,y))$。

于是有递推

$$F(x,y)=\max\left(0,1+\max\left(F(R(x,y)),F(t,t)\right)\right),$$

其中 $t=p_0(\min(x,y))$，而

$$R(x,y)= \begin{cases} (p_1(x),y),&p_1(x)>p_2(y),\\ (x,p_2(y)),&\text{否则}. \end{cases}$$

参数为负的状态不可行。每次转移都会减小 $x+y$。

做法

算法一：单元格占用集合 DP

当 $n\le8$ 时，枚举全部三个种类的零和矩形，把它们转成不超过 $16$ 位的单元格占用掩码。随后做 0/1 集合 DP，只有当前掩码与新矩形不相交时才能加入。

算法二：二维 DP

当 $n\le2000$ 时，按 $x+y$ 递增枚举所有 $(x,y)$，直接使用上述递推。所有依赖状态的坐标和更小，因此可以自底向上求值。

算法三：按需状态压缩

从 $(n,n)$ 开始，只把递推真正访问到的状态加入记忆表。对每个 $i$，重要状态只有 $(i,i)$，以及答案恰比 $F(i,i)$ 多一的两个最早非对角状态；若一侧已经连续加入两个或更多行内矩形，就能先把较短侧跳到同一列而不损失最优性。因此可达状态总数为 $O(n)$。

标程用显式栈后序求值这些状态，避免 $n=300000$ 时递归栈过深。独立核验程序先生成整个可达状态 DAG，再按 $x+y$ 排序求值。

正确性证明

任意好矩形只能是第一行区间、第二行区间或同时占两行的区间。固定已允许的前缀 $(x,y)$，取最优方案中最右侧结束的矩形。若选两行矩形，删除它后剩余方案完全位于某个相同前缀 $(t,t)$，取最靠右的合法左端点 $p_0(\min(x,y))$ 最优。若选单行矩形，两个候选的左端点分别是 $p_1(x)$ 与 $p_2(y)$；选择左端点更靠右者会保留另一行更多可用单元格，另一选择不可能更优。故递推穷尽最优方案且不引入相交矩形。基础值零对应不选任何矩形，归纳可知 $F(n,n)$ 即答案。

复杂度

三档算法的时间复杂度分别为 $O(3n^2 2^{2n})$、$O(n^2)$ 与期望 $O(n)$，空间复杂度分别为 $O(2^{2n})$、$O(n^2)$ 与 $O(n)$。前缀和位置表使用哈希表构造，满分算法的总期望复杂度为 $O(n)$。