10774: matrix

题目描述

现在有一个n*m的01矩阵，矩阵的行与行可以互相交换，我们现在想知道在一个最优的交换方案中，其中最大的全1子矩阵能有多大。

 

输入

第一行两个整数n，m。

接下来n行，每行一个长度为m的01字符串，描述这个01矩阵。

 

 

输出

一个数，即最大的全1子矩阵面积。

 

样例输入

复制样例数据

2 21011

样例输出

2

 

提示

对于30%的数据，n,m<=10。

对于70%的数据，n,m<=1000。

对于100%的数据，n,m<=5000。

 

寒假的题 碰到类似的 就回来写一下

 

思路：

用sum[i][j]记录 第i行 到第j列这个位置

连续的1的数量

然后从1开始枚举每一列，用cnt[i]记录

到这一列中连续出现i个的数量，那么i*cnt[i]就是换行之后出现的各种矩形的面积

注意cnt[i] cnt[j] 若i>j 相乘的时候 j = j+i    ( 就是短的也可以用长的 )

代码：

#include 
       
         using namespace std;const int maxn = 5005;int Map[maxn][maxn]; int main(){    int n,m;    char s[maxn];    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)    {        scanf("%s",s+1);        for(int j=1;j<=m;j++)        {            Map[i][j] = s[j]-'0';            if(Map[i][j])                Map[i][j] += Map[i][j-1];        }    }     int ans = 0;    int maxx = m;    int cnt[maxn]={
     0};    for(int j=1;j<=m;j++)    {        for(int i=0;i<=n;i++)  //str[i][j] 为到这一列的连续长度        {            if(Map[i][j]!=0)            {                cnt[Map[i][j]]++;            }        }        for(int i=m;i>=1;i--)        {            ans = max(ans,i*cnt[i]);            cnt[i-1]+=cnt[i];            cnt[i] = 0;        }    }    printf("%d\n",ans);    return 0;}