题解 AGC033D【Complexity】

problem

定义一个 0/1 矩阵 \(B\) 的复杂度为：

• 若 \(B\) 只由一种数字组成，其复杂度为 \(0\)。
• 否则，用一条平行于矩阵 \(B\) 任意一边的直线将 \(B\) 划分为两部分，则复杂度为所有划分方案中 两个子矩阵的复杂度的最大值加一 的最小值。

求出一个 \(n\times m\) 的 0/1 矩阵 \(A\) 的复杂度。\(n,m\leq 200\)。

solution

naive 的 DP：令 \(f(l,r,d,u)\) 表示 \(A\) 的一个子矩阵取 \(i\in[l,r],j\in[d,u]\) 的部分的复杂度。转移枚举直线，\(O(n^5)\)。

考虑：

• 答案的下界：每次对半分矩阵，形成一棵满二叉树，深度 \(\log n+\log m=\log nm\)。
• \(f\) 随便拎出一维，都有单调性，显然的。

令 \(f(ans,l,r,d)\) 表示，当我们固定了答案为 \(ans\)，已知 \([l,r],d\) 求最大的 \(u\)（有 LGP3147 内味了）。

转移：假如我们说

原文地址：http://www.cnblogs.com/caijianhong/p/solution-agc033d.html