当前位置:编程学习 > wap >>

HDU 2830 Matrix Swapping II

枚举所有的行,然后对于每个行,记录到这行为止每列连续的1的个数,我们可以把每列看做宽度为1,

连续个数看做它的高度。

然后问题就可以看做在一些高度可能为0的相邻矩形中找到最大矩形,即最大长方形那道题(HDU 1506)

应该注意的是列能任意移动,那么将高度从大到小排序是最优的求解方法,然后有b[i-1]>=b[i],

面积显然是h[i] * i . 然后枚举.

[cpp]
#include <cstdio> 
#include<iostream> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
int a[1010],b[1010]; 
bool cmp(int t1,int t2) 

     return t1>t2; 

int main() 

    int i,j,n,m,len,ans; 
    char ch[1001]; 
    while(scanf("%d%d",&n,&m)!=EOF) 
    { 
       memset(a,0,sizeof(a)); 
       ans=0; 
       for(i=1;i<=n;i++) 
       { 
          scanf("%s",ch); 
          len=strlen(ch); 
          for(j=0;j<len;j++) 
          { 
            if(ch[j]=='1') 
                a[j+1]++; 
            else a[j+1]=0; 
            b[j+1]=a[j+1]; 
          } 
          sort(b+1,b+1+m,cmp); 
        for(j=1;j<=m&&b[j];j++) 
            if(b[j]*j>ans) ans=b[j]*j; 
       
       } 
       printf("%d\n",ans); 
    } 
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,