当前位置: 代码迷 >> 综合 >> HDU 2830 Matrix Swapping II *
  详细解决方案

HDU 2830 Matrix Swapping II *

热度:108   发布时间:2023-09-23 06:41:21.0

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2830

额 这题目思路太巧妙了

h[]保存从从第一行起连续的1的数量

1011      1011

1001 -> 2002

0001     0003   

再因为列数是可以变的 所以,直接把该行所有1都往右移

第一层有三个1,变为0111, 所以ans=3*1和2*1和1*1

第二层有2个1,变为0022, 所以ans=2*2和2*1

第三层有1个1,变为0003,所以ans=3*1

再选最大的就是4

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1000+5;
int temp[maxn],h[maxn];
char Matrix[maxn][maxn]; 
int main()
{int R,C;while(scanf("%d%d",&R,&C)!=EOF){memset(h,0,sizeof(h));for(int i=0;i<R;i++)scanf("%s",Matrix[i]);int ans=0;for(int i=0;i<R;i++){for(int j=0;j<C;j++)if(Matrix[i][j]=='1') h[j]++;  else  h[j]=0;memcpy(temp,h,sizeof(h));sort(temp,temp+C);for(int j=0;j<C;j++)ans=max(ans,temp[j]*(C-j));}cout<<ans<<endl;}return 0;
}


  

  相关解决方案