hdoj1830

    可以说这题依然是前面最大子矩阵的加强版,这一次列之间可以无限交换。

    思路:枚举以每一行为底,这样可以求出h[]数组。因为列可以交换所以将h[]数组降序排列,显然以h[1]为高的矩形面积是h[1]*1,以h[2]为高的矩形面积是h[2]*2……。找出这些矩形中最大的即为以i行为底的h[]数组所能形成的最大子矩阵,剩下的就是枚举行

 

 

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char map[1010][1010];
int h[1010];
bool cmp(int a,int b)
{
	return a>b;
}
int cal(int h[],int m)
{
	int i;
	int ans=-1;
	for(i=1;i<=m;i++)
	{
		int tmp=h[i]*i;
		if(tmp>ans)
			ans=tmp;
	}
	return ans;
}
int main()
{
	int n,m;
	int i,j,k;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		getchar();
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%c",&map[i][j]);
			}
			getchar();
		}
		int ans=-1;
		for(i=1;i<=n;i++)
		{
			memset(h,0,sizeof(h));
			for(j=1;j<=m;j++)
			{
				for(k=i;k>=1;k--)
				{
					if(map[k][j]=='1')
						h[j]++;
					else
						break;
				
				}
			}
			sort(h+1,h+1+m,cmp);
			int tmp=cal(h,m);
			if(tmp>ans)
				ans=tmp;
		}
		printf("%d\n",ans);
	
	}

//system("pause");
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>