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

· · 题解

前言：感觉大佬们只讲了怎么做，没写为什么要这么做 ，不适合我这种蒟蒻理解。所以我写了篇适合蒟蒻食用的题解。

题意

楼梯：左侧齐平，右侧不能往左陷

思路

根据题意，我们先记 h_{i,j}，代表 (i,j) 右侧有几个 1。

然后，把模板横过来，发现题目就是让我们找最长不下降子串的每一项之和（不过有很多行）。

大体思路有了，现在要实现找每行（横着的）最长不下降子串。

首先，我们从右往左一列一列看（横着的从上到下），记录这格的 h_{i,j} 能从下往上延续多少格，记延续的格数 l_{i}（由于每行是单独的，行内计算可以省略 j），那么这个 h_{i,j} 能做出 l_i \times h_{i,j} 格贡献（请搭配题图理解）。

然后，我们从上往下（横着的从左到右）遍历，记以当前格为左下角（正看）的楼梯的面积为 s_i，s_i = s_{i - l_i} + l_i \times h_{i,j}。也就是当前 h_{i,j} 做的贡献加上前面它结束贡献的地方的贡献。以样例为例，j = 2 时，两格的楼梯持续了两个长度，那么 s_4 = s_2 + l_5 \times h_{5,2}。

不过直接模拟时间复杂度是 O((hw)^2)，会 TLE，我们要优化一下。

我们寻找最长不下降子串的特点是：从右到左，找第一个小于 h_{i,j} 的地方。所以我们能想到用单调栈来优化。单调栈能把时间优化成 O(hw)。

我们的思路到此结束，接下来就要开始写代码啦~

代码

#include <bits/stdc++.h>
using namespace std;
vector<vector<bool>> a;
vector<vector<int>> h;  // 以(i,j)为准，右边有多少个1
vector<int> s,l;
// s：对于每个j，以i为左下角的楼梯的最大格数
// l：对于每个j，h[i][j]能向上持续多远（楼梯定义）
int mx;
int main(int argc, char **argv){
    int n,m;
    cin >> n >> m;
    a = vector<vector<bool>>(n + 1,vector<bool>(m + 1));
    h = vector<vector<int>>(n + 1,vector<int>(m + 1));
    s = l = vector<int>(n + 1);
    for (int i = 1;i <= n;i++){
        string s;
        cin >> s;
        for (int j = 1;j <= m;j++){
            a[i][j] = s[j - 1] - '0';
        }
    }
    for (int i = 1;i <= n;i++){
        h[i][m] = a[i][m];
        for (int j = m - 1;j > 0;j--){
            if (a[i][j])    h[i][j] = h[i][j + 1] + 1;
        }
    }
    for (int j = m;j > 0;j--){
        // for (int i = n;i > 0;i--){
        //  int k = i - 1;
        //  while (k >= 0 && h[k][j] >= h[i][j])    k--;
        //  l[i] = i - k;
        // }
        // for (int i = 1;i <= n;i++){
        //  s[i] = s[i - l[i]] + l[i] * h[i][j];
        //  mx = max(mx,s[i]);
        // }
        stack<int> st;
        for (int i = n;i > 0;i--){
            l[i] = i;   // 默认能持续到最顶上
            while (!st.empty() && h[st.top()][j] > h[i][j]){
                l[st.top()] = st.top() - i;
                st.pop();
            }
            st.push(i);
        }
        for (int i = 1;i <= n;i++){
            s[i] = s[i - l[i]] + l[i] * h[i][j];
            mx = max(mx,s[i]);
        }
    }
    cout << mx;
    return 0;
}

upd 2025.10.7：纠正一处笔误。