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 内味了）。
转移：假如我们说
标签：log,题解,复杂度,矩阵,Complexity,ans,AGC033D From： https://www.cnblogs.com/caijianhong/p/solution-agc033d.html