宝库通道

【题目描述】

大厅地面是由相同的正方形石块组成的一个m*n的矩阵，这些石块分为黑、白两色（1表示黑色，0表示白色），在其中一块石块的下面存在着宝库通道。

据藏宝图记载，通道存在于某一特定的区域内，这个区域是由数个石块组成的一个小矩形。如果对整个大厅地面任意划分矩形，那么在所有矩形中，这个区域的黑色石块数目减去白色石块数目所得的差是最大的。

【输入描述】

第一行输入两个整数m、n (1 <= m,n <= 400)；

接下来m行，每行输入n个01字符。

【输出描述】

输出一个数，表示所有可能区域中最大的S值。

【样例输入】

3 4

1011

1111

1111

【样例输出】

10

源代码：

#include<cstdio>
int m,n,Max(0),Map[400][400],f[400]; //这次开省了。
int main()
{
    scanf("%d%d",&n,&m);
    for (int a=0;a<n;a++)
      for (int b=0;b<m;b++)
      {
        scanf("%1d",&Map[a][b]);
        Map[a][b]=Map[a][b]==1?1:-1; //转化为了最大子矩阵和，值得借鉴。
      }
    for (int a=0;a<n;a++) //枚举矩阵上界。
      for (int b=a;b<n;b++) //枚举矩阵下界。
      {
        int t(0); //注意循环次序，按此循环其实是一种前缀和。
        for (int c=0;c<m;c++) //利用了最大子序列和的思想，化二维为一维。
        {
            if (a==b)
              f[c]=Map[a][c];
            else
              f[c]+=Map[b][c];
            t+=f[c];
            t=t<0?0:t;
            Max=Max<t?t:Max;
        }
      }
    printf("%d",Max);
    return 0;
}