题解：P12501 「ROI 2025 Day1」奥林匹克楼梯

__FL__ · 2025-08-10 18:13:58 · 题解

Solution

楼梯的形状是一个矩形的残缺，我们不妨考虑它完整的那一个角。考虑当一个方格作为楼梯的左下角时，它的最大格子数量是确定且好求的。显然，从下往上每一行都尽量往右拓展，得到的值是最大的。

考虑单调栈维护。设 sum_{i,j} 表示方格 (i,j) 往右最多能拓展多少个 1；枚举每一列，从上往下将 sum_{i,j} 加入单调栈，对于每一个格子，取它的最大值。

时间复杂度 O(hw)。

Code

#include <bits/stdc++.h>
using namespace std;
int h,w,ans;
stack<pair<int,int>>s;
signed main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> h >> w;
    char a[h+5][w+5];
    int sum[h+5][w+5];
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
        {
            cin >> a[i][j];
            if (j == w) sum[i][j] = a[i][j]-'0';
            else sum[i][j] = 0;
        }
    for (int i = 1; i <= h; i++)
        for (int j = w-1; j >= 1; j--)
            if (a[i][j] == '1') sum[i][j] = sum[i][j+1]+1;
    for (int i = 1; i <= w; i++)
    {
        while (!s.empty()) s.pop();
        int tot = 0;
        for (int j = 1; j <= h; j++)
        {
            int p = 1;
            while (!s.empty() && sum[j][i] <= s.top().first) tot += (sum[j][i]-s.top().first)*s.top().second,p+=s.top().second,s.pop();
            s.push({sum[j][i],p});
            tot += sum[j][i];
            ans = max(ans,tot);
        }
    }
    cout << ans;
    return 0;
}