Maximum Submatrix 2

Codeforces Round #221 (Div. 1) B:http://codeforces.com/problemset/problem/375/B

题意:给你一个n*m的0,1矩阵,你可以交换一些行,求一个最大子矩阵的面积,这个子矩阵全部包含1.

题解:看标签是数据结构,怎么想,也不知道用数据结构怎么搞。最后想到是求面积,面积不就是l*d,只要确定了了l和d,面积就出来了,于是我想到了枚举l和d。这里要先处理出来一些东西,dp[j][i]表示(i,j)的右边的有多少个连续的1,包括(i,j),可以这么想,矩阵的左边一定出现在那一列,所以可以枚举列,对于固定左边来说,也就是起点固定了,那么狠容易想到,,要把连续1多的放在一起,所以要对该列进行排个序,然后就可以开始枚举,从上到下,因为最上面的是最短的,所以下面构成的面积才是我们想要的。得到最大的面积。表述不是很清晰,还是看代码吧。题解说用基数排序,但是我用了基数排序,发现比类库的排序要慢,也许是数据小的原因吧。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,m,r[N][N];
char mp[N][N];
bool temp[N];
/*int counts[N],tmp[N];
int maxbit(int x){
int d=1;
for(int i=1;i<=n;i++){
int c=1;
int p=r[x][i];
while(p/10){
p=p/10;
c++;
}
if(c>d)
d=c;
}
return d;
}
void RadixSort(int x){
int d=maxbit(x);
int rr=1;
for(int i=0;i<d;i++){
for(int j=0;j<10;j++)
counts[j]=0;
for(int j=1;j<=n;j++) {
int k=r[x][j]/rr;
int q=k%10;
counts[q]++;
}
for(int j=1;j<10;j++){
counts[j]+=counts[j-1];
}
for(int j=n;j>=1;j--)
{
int p=r[x][j]/rr;
int s=p%10;
tmp[counts[s]-1]=r[x][j];
counts[s]--;
}
for(int j=0;j<n;j++){
r[x][j+1]=tmp[j];
}
rr=rr*10;
}
}*/
int main(){
while(~scanf("%d%d",&n,&m)){
memset(r,,sizeof(r));
for(int i=;i<=n;i++)
scanf("%s",mp[i]+);
for(int i=;i<=n;i++){
int temp=;
for(int j=m;j>=;j--){
if(mp[i][j]==''){
temp=;
}
else
temp++;
r[j][i]=temp;
}
}
int ans=;
for(int i=;i<=m;i++){
//RadixSort(i);
sort(r[i]+,r[i]+n+);
for(int j=;j<=n;j++){
ans=max(ans,r[i][j]*(n-j+));
}
}
printf("%d\n",ans);
}
}
上一篇:update 问题


下一篇:查询拼接SQL语句,多条件模糊查询