洛谷 P12501 分析（别看）

科技起源的小号1

2026-08-24 21:03:34

发布于：天津

5阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

背景：
有一个 $h\times w$ 的 $0/1$ 矩阵
楼梯是由若干连续行中填有 1 的格子集合组成的。在每一行中，被选中的格子必须形成一个连续的段。
同时，满足以下条件：

每下一行的选中格子数量不得少于紧邻其上的上一行
每行中最左边的选中格子必须位于同一列

允许：
矩阵中 $1$ 代表可以作为楼梯的一部分
求这个楼梯最多可以由多少 $1$ 组成

1.3 题目数据范围与猜测

$h\times w \le 2\times10^5\rightarrow O(hw)$

1.4 一句话概括题意

有一个矩阵，求这个矩阵中构成楼梯的最大值

2 题目破题推导

2.1 第一步：以终为始

要想得到最大楼梯，楼梯一定是这样的

-------
|  |  |---
|  |  |  |
|  |  |  |---  
|  |  |  |  |

也就是若干个相同高度的+逐渐比自己低的，比自己后面低的，比自己后面的后面低的...

2.2 第二步：分情况讨论

当前这一项和自己一样高
那太好了，可以直接加入我们的楼梯队列中
当前这一项比自己高
那也没关系，可以把上面那部分消掉
当前这一项比自己矮
那很可惜，它只能间接地作为我的后面了（当然有可能不适用）
这里之所以是间接的，因为有可能我的后面，它的前面有和它一样高的或者比它矮的

2.3 第三步：边界思维

注意不存在右边比自己矮的柱子的情况，dp应该直接置 $0$

3 模型匹配

单调栈模板
这里需要维护单调递增栈，为了维护当前点后面第一个比自己低的
dp的时候循环是从 $w$ 到 $1$ ，这样才能依靠之后列的答案推前面的若干列
然后dp就可以是：

$dp[i] = dp[r[i]] + a[i] * (r[i] - i)$

$dp[i]$ 表示考虑到第 $i$ 列，最大楼梯大小
$r[i]$ 表示当前这个柱子右边（后面）第一根比自己矮的
$dp[r[i]]$ 表示右边（后面）第一根比自己矮的柱子最多有多少
$a[i]$ 表示当前这根柱子高度
$r[i] - i$ 表示当前这个柱子到右边第一个比它矮的柱子之间的距离，高度 $\times$ 距离 $=$ 整体方块大小，这里不需要考虑消去的那部分，因为那部分根本没算进来
两部分相加就可以得到当前答案

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int h, w;
const int N = 2e5 + 10;
int a[N];
int r[N];
int dp[N];

int main(){

    cin >> h >> w;
    int ans = INT_MIN;
    while(h--){
        for (int i = 1;i <= w;i++){
            char ch;
            cin >> ch;
            a[i] = (ch == '1' ? a[i] + 1 : 0);
        }
        stack<int> st;
        for (int i = 1;i <= w;i++){
            while(!st.empty() && a[st.top()] > a[i]){
                r[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        while(!st.empty()){
            r[st.top()] = w + 1;
            st.pop();
        }
        for (int i = w;i >= 1;i--){
            dp[i] = dp[r[i]] + a[i] * (r[i] - i);
            ans = max(ans, dp[i]);
        }
    }
    cout << ans;
    
    return 0;
}