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

__liujy · 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;
}