PROBLEM 2.石材切割

问题描述：

某人得到一块N*M个小格的矩形石材（可能是玉石），经专家分析，把这个矩形石材的每个小格都有一个价值（使用一个绝对值不大于10的整数来描述），现在将这块石材切割成两块矩形石材，注意，切割只能与该矩形边平行，也就是说不能把矩形的小格切碎，假设每块矩形石材的价值为该矩形中所有小格子价值之和。

    问怎样切割，才能使得这两个矩形的价值乘积最大。如下图是一种比较好的切割方式。

输入格式：

输入文件BRICK.IN的第一行为2个正整数N和M，表示石材被划分为N*M个格子。接下来N行，每行有M个整数，代表这个格子的价值。

输出格式：

输出文件BRICK.OUT只有一行，包含一个整数，为两个矩形的价值的最大乘积。

数据范围

对于30%的数据，满足N,M≤5。

对于100%的数据，满足N,M≤100。每个小格的伤害值的绝对值不超过10。

一切数据及中间变量不超过longint范围。

做此题时脑子没有转过来，其实还是比较简单的，就是最大子矩阵的变种问题，首先题中需要的是两部分乘积，因此可以先把图划为2部分，再在两部分中分别求出最大，之后相乘记录最优，因为可以明确，划分为2部分必然是横着切一下或者竖着切一下。没有其他情况，所以可以分类讨论。就拿竖着切来说吧，可以先用平时求最大子矩阵的方法维护出一个f[i,j]表示第i列到第j列包含i，j边界的最大矩形的面积，这一个处理可以用N^3实现，之后枚举i1,j1,i2,j2求出最大的f[i1,j1]*f[i2,j2]敝人比较菜只会这么处理。。因为这是4方的枚举10^8有可能超时，不过这并不是严格的4方因为有j1>=i1,i2>j1,j2>=i2。想一下如果一个2方的枚举j<=i的话那么就是(1+2+3+......+n)=(n+1)*n/2的时间复杂度比普通的节省一半，所以这个4方枚举明显在5*10^7一下绝对不会超时的。。。实际上最慢的一个只用了0.1s

另外要注意的是此题还有负数，也就是说2个极小值相乘也可能最大，所以本题一共要分4类求解出最大。代码就不说了吧