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