自动搬运

查看原文

来自洛谷，原作者为

	__liujy 芳龄 12 的老爷爷。

搬运于2025-08-24 23:16:01，当前版本为作者最后更新于2025-07-08 08:53:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目中的 $h$ 和 $w$ 在文中用 $T$ 和 $n$ 代替。

设一个楼梯的最下端在第 $T$ 行，这样就能从改行往上枚举。

设楼梯的左下角为 $(T,l)$，从左往右贪心，每一次让楼梯尽量高就是最优的。

这个过程可以用单调栈优化，优化的部分为 $i=l$ 开始，考虑 $a_{i}$ 贡献了多少次，找出 $i$ 后第一个小于 $i$ 的位置 $r_{i}$，则 $a_{i}$ 的贡献为 $a_{i} \times (r_{i}-i)$，然后每一次 $i=r_{i}$ 往下继续枚举。

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5;
int T,n,a[N],r[N],val[N],ans;
int main()
{
	cin>>T>>n;
	while(T--)
	{
		for(int i=1;i<=n;i++)
		{
			char ch;
			cin>>ch;
			a[i]=(ch=='0'?0:a[i]+1);
		}
		stack<int> st;
		for(int i=1;i<=n;i++)
		{
			while(st.size()&&a[st.top()]>a[i])
			{
				r[st.top()]=i;
				st.pop();
			}
			st.push(i);
		}
		while(st.size())
		{
			r[st.top()]=n+1;
			st.pop();
		}
		for(int i=n;i>=1;i--)
		{
			val[i]=val[r[i]]+a[i]*(r[i]-i);
			ans=max(ans,val[i]);
		}
	}
	cout<<ans<<'\n';
	return 0;
}