hdu 2830 Matrix Swapping II（额，，排序？）

浏览数：66 / 时间：2015年06月11日

题意：

N*M的矩阵，每个格中不是0就是1。

可以任意交换某两列。最后得到一个新矩阵。

问可以得到的最大的子矩形面积是多少（这个子矩形必须全是1）。

 

思路：

先统计，a[i][j]记录从第i行第j列格往上连续的0的个数。

枚举每一行作为答案子矩阵的底， 然后将这一行的a[i][j]从大到小排序，扫一遍计算。

看代码。

 

代码：

int n,m;
char temps[1005][1005];
int a[1005][1005];
 int ts[1005];



bool cmp(int a,int b){
    return a>b;
}


int main(){

    while(scanf("%d%d",&n,&m)!=EOF){
        rep(i,0,n-1){
            scanf("%s",temps[i]);
        }
        mem(a,0);
        rep(i,0,m-1) if(temps[0][i]==‘0‘) a[0][i]=0; else a[0][i]=1;
        rep(i,1,n-1){
            rep(j,0,m-1){
                if(temps[i][j]==‘1‘) a[i][j]=1+a[i-1][j];
            }
        }

        int ans=0;
        rep(i,0,n-1){
            rep(j,0,m-1) ts[j]=a[i][j];
            sort(ts,ts+m,cmp);
            rep(i,0,m-1) ans=max( ans,ts[i]*(i+1) );
        }

        printf("%d\n",ans);
    }

    return 0;
}

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： Android iOS 移动互联 终端开发

相关文章

随机文章

您可能还喜欢

您可能还喜欢