有一天,小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地.
这片土地被分成 N×MN\times MN×M 个格子,每个格子里写着 R 或者 F,R 代表这块土地被赐予了 rainbow,F 代表这块土地被赐予了 freda.
现在 freda 要在这里卖萌.它要找一块矩形土地,要求这片土地都标着 F 并且面积最大.
但是 rainbow 和 freda 的 OI 水平都弱爆了,找不出这块土地,而蓝兔也想看 freda 卖萌(她显然是不会编程的......),所以它们决定,如果你找到的土地面积为 SSS,它们每人给你 SSS 两银子.
输出一个整数,表示你能得到多少银子,即"3×3\times3×最大 F 矩形土地面积"的值.
典型求最大子矩阵和问题,即求一个 M×NM \times NM×N 矩阵中的子矩阵元素和的最大值.这可以用单调栈解决.对于每一行的每一列元素,往上计算连续的 F 的个数,即得到以每一行为基准的一个条形统计图,每个列对应一个条形矩形,矩形的宽为 111 ,高即为该元素往上计算连续的 F 的个数,这就是典型的计算矩形统计图的最大内矩形面积的问题,用 O(N)O(N)O(N) 的单调栈完美解决.由于有 NNN 行,每一行都构造出一个矩形统计图,故总复杂度为 O(N2)O(N^2)O(N2) .