[牛客] 麻将

恶灬心 · 2019-08-23 10:55:10 · 个人记录

题面

这道题是一道dp题。

首先，对于这个01矩阵，列的顺序是固定的，而行可以改变。

那么说明，我们只要枚举行排列所有情况，在对其进行dp找出最大矩阵就能完成任务。

但是，直接枚举时间爆炸。

于是，我们观察答案矩阵的一些性质。 答案矩阵必定是全1矩阵，说明对于整个矩阵来说，答案矩阵必定是连续一段的，每行的一段列上必定都是1。

那么，我们首先对列进行处理。 处理出连续出现1的长度。

这样，我们就能得出每行在k列处，连续的最长段的长度。

接着，观察行的情况，和列一样，答案矩阵每行每列必定为1，现在行的顺序不确定，但我们已知每行上每列的情况，只需要枚举列，然后让尽可能多的1汇聚在一起就行。

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int w=1,d=0; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')d=d*10+ch-'0',ch=getchar();
    return w*d;
}
int n,m;
bool a[5010][5010];
int f[5010][5010];
int d[5010];
int main()
{
    n=read(),m=read();
    for(register int i=1;i<=n;i++)
    for(register int j=1;j<=m;j++) a[i][j]=read();
    for(register int i=1;i<=n;i++)
    for(register int j=1;j<=m;j++)
    f[i][j] = a[i][j]==0 ? 0 :f[i][j-1]+1;
    long long ans = 0; 
    for(register int j=1;j<=m;j++)
    {
        for(register int i=1;i<=n;i++) d[i]=f[i][j];
        sort(d+1,d+1+n);
        for(register int i=1;i<=n;i++) ans = max(ans,(long long)d[i]*(n-i+1));
    }
    cout<<ans;
}