CF375B 题解

SkyRainWind · 2023-03-12 21:29:54 · 题解

这道题，当时 18 年在浙江培训的时候做过几乎一样的原题，叫《说好的一起富起来呢贺爸你怎么不等我》，青春易逝啊，挺感慨的。

题目本身非常简单，甚至不需要动态规划。

注意到行是可以随便换的，因此从第 m 列到第 1 列递推，每次只与当前列右边第一串 1 的个数有关，这样每次就可以从第 i+1 列递推到第 i 列，就记一下极长的 1 个数，然后逆序排序统计答案即可。

直接实现是 O(n^2\log n) 的，由于 n=5000 还是通不过的。考虑优化：

注意到每次如果当前列当前行是 1 的话，其实相对大小是不会变的，如果是 0 的话就挪到最后，这样每次用类似归并排序的想法就可以做到线性的合并了，时间复杂度 O(n^2)。

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 5005;

int n,m,a[maxn][maxn];
pii sum[maxn];  // <sum, id>
pii s[5002];

signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        char s[5005];scanf("%s",s + 1);
        for(int j=1;j<=m;j++)a[i][j] = s[j] - '0';
    }
    int ans = 0;
    for(int j=1;j<=n;j++)
        if(a[j][m] == 1)sum[j] = mpr(1, j), ans = 1;
        else sum[j] = mpr(0, j);
    sort(sum+1,sum+n+1,[&](pii a,pii b){return a.first > b.first;});

    for(int i=m-1;i>=1;i--){
        int lst = n, fi = 0;
        for(int j=1;j<=n;j++){
            pii v = sum[j];
            if(a[v.second][i] == 0)s[lst --] = mpr(0, v.second);
            else s[++ fi] = mpr(v.first+1, v.second);
        }
        for(int i=1;i<=n;i++)
            ans = max(ans, s[i].first * i), 
            sum[i] = s[i];
    }
    printf("%d\n",ans);

    return 0;
}

青春不朽，青春万岁。