2630 宝库通道

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 黄金 Gold

题目描述 Description

由于你的帮助，小可可终于来到了宫殿的正厅中。大厅的地面是由一块块大小一致的正方形石块组成的，这些石块分为黑、白两色，组成了一个m*n的矩形，在其中一个石块的下面就是通往藏宝库的通道。小可可不可能一个一个石块的尝试，因为有些石块安装了机关，一碰就会触发，整个宫殿也随之倒塌。根据藏宝图记载，通道在某一特定的区域中，这个区域是一个由数个石块组成的面积不为0的小矩形，它的四条边与大厅地面的边平行。如果对整个大厅地面任意划分矩形，那么在所有矩形中，这个区域的黑色石块数目减去白色石块数目所得的差是最大的。

小可可希望和你分工，由他来选择区域，你来计算黑、白两色石块的数目差S。这样就能快速而准确的确认通道所在的区域。藏宝图上说这个区域中的石块都没有安装机关，只要确定了区域，就一定能找到通道。宝藏就在眼前了，加油吧！

（假设用1表示黑色石块，用0表示白色石块）

输入描述 Input Description

输入：输入文件的第一行为两个整数m,n (1<=m,n<=400).

以下m行，每行n个字符，每个字符都是0或1。

输出描述 Output Description

输出：输出文件仅一个数，表示所有可能的区域中S值（见前文描述）最大的一个，输出这个值即可。

样例输入 Sample Input

输入：

3 4

1011

1111

样例输出 Sample Output

输出：

数据范围及提示 Data Size & Hint

(1<=m,n<=400)

分类标签 Tags 点此展开

AC自动机

题解：

枚举端点+最大子段和O(n)算法

总 O(n^3)

AC代码：

#include<cstdio>
using namespace std;
const int N=1e3+10;
int n,m,ans,s[N],a[N][N];
void deal(){
    int b=0;
    for(int i=1;i<=n;i++){
        if(b>0) b+=s[i];
        else b=s[i];
        if(ans<b) ans=b;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%1d",&a[i][j]);
            if(!a[i][j]) a[i][j]=-1;
            a[i][j]+=a[i][j-1];
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=i;j<=m;j++){
            for(int k=1;k<=n;k++) s[k]=a[k][j]-a[k][i-1];
            deal();
        }
    }
    printf("%d
",ans);
    return 0;
}