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

Solution

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

考虑单调栈维护。设

sum_{i,j}

表示方格

(i,j)

往右最多能拓展多少个

1

；枚举每一列，从上往下将

sum_{i,j}

加入单调栈，对于每一个格子，取它的最大值。

时间复杂度

O(hw)

。

Code

CPP

#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;
}

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

文章操作

Solution

Code

相关推荐

评论

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