1621. 未命名

---

Description

人总会有没灵感的时候。

没灵感的时候，出的题多半都是平凡的Idea堆出来的。

这大概是个懒题，我也不太有想法给它取个好名字。

现在有一个n×n的黑白矩阵，我想找到一个面积最大的全白子矩形。

这次你获得了某种特权，你似乎可以随意交换两行任意多次，于是你可以获得一个更好一点的答案。

于是请你轻松随意的把这题写掉吧。

Input Format

第一行是一个数n，描述这个矩阵的大小。

接下来将会读入n行的01字符串来描述这个矩阵。如果是0，就代表这个格子是黑点，否则是白点。

Output Format

一行，输出最大全白子矩形的大小。

Sample Input

2

11

11

Sample Output

4

Limits

对于40%的数据，n <= 8

对于100%的数据，n <= 1000

solution

思路

• 我们枚举矩阵的左边界l
• 然后统计以左边界l为起始第i行连续的 1 的长度sum[i];
• 对sum[i]从小到大进行排序

例如

对于这个矩阵

110

101

111

可以看作

101

110

111

• 然后,枚举有边界r
• r=1时,最大矩阵是

101

110

111

s=3

• r=2时,最大矩阵是

101

110

111

s=4

• r=3时,最大矩阵是

101

110

111

s=3

• 所以最大子矩阵面积即为4

正确性

• 注意,矩阵任意两行都可以互换
• 所以,排序后逐个枚举边界是可行的

算法

数组 XD

code

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define re register intusing namespace std;const int maxn=1005;int g[maxn][maxn],sum[maxn];char s[maxn][maxn];int n;inline int get_s(int x){    memset(sum,0,sizeof(sum));    bool tmp=1;    for(re i=1;i<=n;++i) for(re j=x;j<=n;++j) {        if(g[i][j]==1) sum[i]++;        else break;    }    sort(sum+1,sum+n+1);    int ans=-150;    for(re i=1;i<=n;++i) {        ans=max(ans,(sum[i]*(n-i+1)));    }    return ans;}int main(){    //freopen("1621.in","r",stdin);    //freopen("1621.out","w",stdout);    scanf("%d",&n);    for(re i=1;i<=n;++i) scanf("%s",s[i]+1);    for(re i=1;i<=n;++i) for(re j=1;j<=n;++j) g[i][j]=s[i][j]-48;    int ans=-150;    for(re j=1;j<=n;++j) {        int k=get_s(j);        ans=((ans>k)?ans:k);    }    printf("%d",ans);    return 0;}
         
        
       
      
     

​