noj 1017 最大零矩阵.txt

NUAA ACM OJ源码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;

/*NOJ 1017
算法简介：
设h[i, j]为元素a[i j]的高度,其定义如下:
若a[i j]为1,则h[i, j]=0,否则定义为从该元素开始在同一列上向上延伸的连续的零(0)的个数.考虑面积最大的全零(0)子矩阵的最后一行,则要求的面积最大的全零(0)子矩阵的高度必为其最后一行所有零(0)元素中高度最小的元素的高度,否则该子阵必不是最大的,与假设矛盾.
再定义l[i, j]为从第i行第j列开始向左延伸高度均不小于h[i, j]的最左一列的列号,即从该列开始至第j列的每个元素的高度均不小于h[i,j],同样定义r[i, j]为从第i行第j列开始向右延伸高度均不小于h[i, j]的最右一列的列号,即从第j列开始至该列的每个元素的高度均不小于h[i,j],
则底边包含元素a[i,j]的面积最大的全零子阵的面积为(r[i,j]-l[i,j]+1)*h[i,j],
而h(i,j),l(i,j),r(i,j)可以逐行递推,递推的方法为增加一个元素值全1的第0行,这不影响问题的解,则根据定义h[0,j]=0, l[0,j]=1,r[0,j]=n,其中1<=j<=n,此为边界条件,且对任意的非零元素上式均适用;
再假设第i行包含第j列的最长的连续全零段最左为第c1列,最右为第c2列,即第i行从第c1列开始至第c2列为止的每个元素的高度均不小于h[i,j],则若递推式为:
h[i,j]=h[i-1,j]+1, l[i,j]=max(l[i-1,j],c1), r[i,j]=min(r[i-1,j,c2]).
对任意的i,j求出(r[i,j]-l[i,j]+1)*h[i,j],其中的最大值即问题的解. 

*/

#define NMAX 2002
int ju[NMAX][NMAX];
int high[NMAX][NMAX];
int l[NMAX][NMAX];
//l[i][j]，第i行以第j列为基准，只要高度小于基准，就向左延伸，最后延伸到的列数
int r[NMAX][NMAX];
//l[i][j]，第i行以第j列为基准，只要高度小于基准，就向右延伸，最后延伸到的列数

int cal(int num)
{
	int i,j,k,min=0,c1,c2;
	//c1，是在第i行包含第j列的全零序列的最左列数
	//c2，是在第i行包含第j列的全零序列的最右列数
	for(i=0;i<=num;i++) high[0][i]=0;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
		{	//计算零列高度
			if(ju[i][j]==1) high[i][j]=0;
			else if(ju[i-1][j]==0) high[i][j]=high[i-1][j]+1;
			else high[i][j]=1;
		}
	}
	for(j=0;j<=num;j++)
	{	//初始化第0行的l[][],r[][]值
		l[0][j]=1;
		r[0][j]=num;
	}
	for(i=1;i<=num;i++)
	{
		//计算l[][],r[][]值
		j=1;c1=1;
		while(j<=num)
		{
			while(ju[i][j]==1)
			{
				l[i][j]=1;//高度为0，可知其向左能延伸到第1列
				j++;
				c1=j;//这个c1显然不合法，修改
			}
			//l[i][j]取l[i-1][j]和c1间的最大值
			if(l[i-1][j]>c1) l[i][j]=l[i-1][j];
			else l[i][j]=c1;
			j++;
		}
		c2=num;k=num;
		while(k>=1)
		{
			while(ju[i][k]==1)
			{
				r[i][k]=num;//高度为0，可知其向右延伸到第num列
				k--;
				c2=k;//这个c2显然不合法，修改
			}
			//r[i][j]取r[i-1][j]和c2间的最小值
			if(r[i-1][k]>c2) r[i][k]=c2;
			else r[i][k]=r[i-1][k];
			k--;
		}
		//max{high[i][j]*(r[i][j]-l[i][j]+1)&&ju[i][j]==0},为所求答案
		for(j=1;j<=num;j++)
		if(min<high[i][j]*(r[i][j]-l[i][j]+1)&&ju[i][j]==0) min=high[i][j]*(r[i][j]-l[i][j]+1);
	}
	return min;
}

int main()
{
	int num,i,j;
	while(scanf("%d",&num)!=EOF)
	{
		for(i=1;i<=num;i++)
		{
			for(j=1;j<=num;j++)
			scanf("%d",&ju[i][j]);
		}
		cout<<cal(num)<<endl;
	}
	return 0;
}
/*
void printh(int num)
{
	int i,j;
	cout<<endl;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			cout<<high[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
}

void printl(int num)
{
	int i,j;
	cout<<endl;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			cout<<l[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
}

void printr(int num)
{
	int i,j;
	cout<<endl;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			cout<<r[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
}
*/