HDU 2830 Matrix Swapping II（最大完全子矩阵之可移动列）

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

/*
题意：
给你一个矩阵，里面的数字只有0和1两种，其中，列可以任意移动。问如何移动可以使某个子矩阵中元素全部是1，求出这个最大子矩阵的面积。

对每一行进行处理然后再叠加，到每一行用num[i]记下到这一行有多少个1

例如：
 
1 0 1 1          num[i]的记录就是： 1 0 1 1                    
 
1 0 0 1                             2 0 0 2         
 
0 0 0 1                             0 0 0 3
 
然后对num[i]从大到小排一下，求出读取到当前行能够得到的最大面积。
 
也就是最右边放着最多的1，依次类推。那么当前最大的面积就是 MAX（max,num[i]*i）了
*/
# include <stdio.h>
# include <algorithm>
# include <iostream>
# include <string.h>
using namespace std;
bool cmp(int x,int y)
{
    return x>y;
}
char a[1010][1010];
int num[1010],ans[1010];
int main()
{
    int n,m,i,j,maxx,k;

    while(~scanf("%d%d",&n,&m))
    {
        for(i=0; i<n; i++)
            scanf("%s",&a[i]);
        memset(num,0,sizeof(num));
        maxx=0;
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                if(a[i][j]=='1')
                    num[j]++;
                else
                    num[j]=0;
                ans[j]=num[j];
            }
            sort(ans,ans+m,cmp);
            for(k=0; k<m; k++)
                maxx=max(maxx,(k+1)*ans[k]);
        }
        printf("%d\n",maxx);
    }
    return 0;
}

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