注意求和方法 http://acm.cs.ecnu.edu.cn/problem.php?problemid=1065  EOJ 1065
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define maxn 1000+5
int a[maxn][maxn],sum[maxn][maxn];
int m,n;
int solve()
{
int ans=0;
int h[maxn],l[maxn],r[maxn];
/*
l[i]：第i列所在的极大化子矩阵的最左端
r[i]：第i列所在的极大化子矩阵的最右端
left：当前行所在的极大化子矩阵的最左端
right：当前行所在的极大化子矩阵的最右端
*/
int left,right;
for(int j=1;j<=n;j++)
{
h[j]=0; l[j]=1; r[j]=n;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]!=0)
h[j]++;
else h[j]=0;
}
left=0;
for(int j=1;j<=n;j++)
{
if(h[j]) //该处是1
l[j]=max(l[j],left);
else //该处为0（“障碍”）
{
left=j+1;//所以能达到的最左端为j+1
l[j]=0; //l[j]置为0是为了在计算第i+1行
}
}
right=n;
for(int j=n;j>0;j--)
{
if(h[j])
r[j]=min(r[j],right);
else
{
right=j-1;
r[j]=n;
}
}
for(int j=1;j<=n;j++)
if(h[j])
ans=max(sum[i][r[j]]+sum[i-h[j]][l[j]-1]-sum[i-h[j]][r[j]]-sum[i][l[j]-1],ans);
}
return ans;
}
int main()
{
int total;
scanf("%d%d",&m,&n);
memset(sum,0,sizeof(sum));
for(int i=1;i<=m;i++)
{
total=0;
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
total+=a[i][j];
sum[i][j]=sum[i-1][j]+total;
}
}
printf("%d\n",solve());
}
|