前四题过水
枚举正方形的上边界所在行。对于第 \(i\) 行一个没洞的位置 \((i,j)\)，我们尝试求出以它为右上角的无洞正方形个数。
结论：设以 \((i,j-1)\) 为右上角的无洞正方形边长最大为 \(len\)，那以 \((i,j)\) 为右上角的无洞正方形边长最大为 \(len + 1\)。
以 \((i,j)\) 为右上角的边长为 \(len+2\) 的无洞正方形包含了以 \((i,j-1)\) 为右上角的边长为 \(len+1\) 的无洞正方形，矛盾。
而以 \((i,j)\) 为右上角边长能为 \(len+1\) 的充要条件是：
-
\((i,j)\) 往下 \(len+1\) 个格子都无洞；
-
\((i,j+len)\) 往左 \(len+1\) 个格子都无洞。
预先记录 \(lft[i][j],dwn[i][j]\) 表示从 \((i,j)\) 往左/下第一次碰到洞是什么地方。\(O(n^2)\) 预处理。
另外，如果 \((i,j)\) 不能达到 \(len+1\)，那边长最大为 \(dwn[i][j]-i+1.\)
然后可以扫一遍行，每行找所有无洞的位置，每个位置 \(ans+=\) 这个位置右上角的最大边长。
\(O(n^2)\)。
（官方发的题解貌似是 dp，\(dp[i][j]\) 表示以 \((i,j)\) 为右下角的无洞正方形个数）
有一个矩阵，一些格子已经被染成黑色。你可以把剩下的格子任意选一些染成黑色。有多少种染色方案使得每个黑格 \((i,j)\)，\((i+1,j)\) 和 \((i+1,j+1)\) 都是黑格？
\(dp[i][j]\) 表示前 \(i\) 列，第 \(i\) 列最高黑格位置是第 \(j\) 行的方案数。
容易发现 \(dp[i-1][j+2\sim n]\) 不能转移到 \(dp[i][j]\)，其他 \(dp[i - 1][]\) 都可以。
同时注意 \(dp[i][j]\) 的 \(j\ge\) 第 \(i\) 列的最高黑格高度。
然后就是正常转移，加上前缀和优化。
找出矩形使得（矩阵和 \(\times\) 矩阵最小值）最大。
直接暴力枚举最小值，然后使用悬线法。
标签：ABC,右上角,311,len,正方形,边长,无洞,dp From： https://www.cnblogs.com/FLY-lai/p/18012021