hdu 2830 Matrix Swapping II

题意:可以任意交换两行,求01矩阵中最大的全1矩阵。

还是和hdu 1505一样的处理方法。

统计的时候学到了一招,我自己想到的是o(N^3)的统计方法,就是只要

不小于当前位置的就tmp++。然后a[i]*tmp,在所有结果中找最大值ans。


这里用到了一个小技巧,就像那个开0-10000的数组作计数器,找n个集合的

交集的那题一样。 

zoj 1143 && poj 1044 Date bugs

这题统计也是用的逐行统计每列高度,用h[j]计数高度j出现的次数。然后逆序扫一遍h数组。

把比当前高度高或者相等的高度个数累加。就可以计算面积了。

h[j]计数高度为j的个数,本来就是升序排列,逆序扫一遍,就从后往前递推着累加了,

刚好可以利用上一个的结果。好巧妙哈哈= =

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

char mp[1005][1005];
int a[1005][1005];
int h[1005];

int main()
{
    int n,m,ans,tmp,t;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
        {
            scanf("%s",mp[i]+1);
            for(int j=1;j<=m;j++)
            {
                if(mp[i][j]==‘1‘)
                    a[i][j]=a[i-1][j]+1;
                else a[i][j]=0;
            }
        }
        /*for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                printf("%d",a[i][j]);
            printf("\n");
        }*/
        ans=-1;
        for(int i=1;i<=n;i++)
        {
            memset(h,0,sizeof(h));
            for(int j=1;j<=m;j++)
                h[a[i][j]]++;
            for(int j=m-1;j>=1;j--)
                h[j]+=h[j+1];
            for(int j=1;j<=m;j++)
            {
                tmp=h[j]*j;
                if(tmp>ans)
                    ans=tmp;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

这题读入矩阵好像非得要用char 数组啊= =

我开始将0 1作为整数读入不行!!


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