题解：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)

。

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

代码

CPP

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#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：纠正一处笔误。

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

文章操作

题意

思路

代码

相关推荐

评论

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