首页 > 代码库 > hdu 2830 Matrix Swapping II（额，，排序？）
hdu 2830 Matrix Swapping II（额，，排序？）
题意：
N*M的矩阵，每个格中不是0就是1。
可以任意交换某两列。最后得到一个新矩阵。
问可以得到的最大的子矩形面积是多少（这个子矩形必须全是1）。
思路：
先统计，a[i][j]记录从第i行第j列格往上连续的0的个数。
枚举每一行作为答案子矩阵的底， 然后将这一行的a[i][j]从大到小排序，扫一遍计算。
看代码。
代码：
int n,m;char temps[1005][1005];int a[1005][1005]; int ts[1005];bool cmp(int a,int b){ return a>b;}int main(){ while(scanf("%d%d",&n,&m)!=EOF){ rep(i,0,n-1){ scanf("%s",temps[i]); } mem(a,0); rep(i,0,m-1) if(temps[0][i]==‘0‘) a[0][i]=0; else a[0][i]=1; rep(i,1,n-1){ rep(j,0,m-1){ if(temps[i][j]==‘1‘) a[i][j]=1+a[i-1][j]; } } int ans=0; rep(i,0,n-1){ rep(j,0,m-1) ts[j]=a[i][j]; sort(ts,ts+m,cmp); rep(i,0,m-1) ans=max( ans,ts[i]*(i+1) ); } printf("%d\n",ans); } return 0;}
hdu 2830 Matrix Swapping II（额，，排序？）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。