hdu 2830 Matrix Swapping II
浏览数：22 /
时间：2015年06月11日
题目大意：
给出的矩阵每一列之间可以任意交换。
求出交换后得到的最大的子矩阵和。
思路分析：
height[i][j] 表示 位置 i j 往下有多少深度。
然后我们枚举每一行。
可以将所有的height 排序。
得到最大的矩阵和就一遍递推过去。
n*n*lgn。。。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define maxn 1005
using namespace std;
int height[maxn][maxn];
char p[maxn][maxn];
int a[maxn];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%s",p[i]);
for(int j=0;j<m;j++)
{
int now=0;
for(int i=n-1;i>=0;i--)
{
if(p[i][j]=='1')now++;
else now=0;
height[i][j]=now;
}
}
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
a[j]=height[i][j];
sort(a,a+m);
int st=0;
while(a[st]==0)st++;
for(int j=st;j<m;j++)
ans=max(ans,a[j]*(m-j));
}
printf("%d\n",ans);
}
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
