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

分析

很明显的单调栈，类似P4147 玉蟾宫。可以用同样的方法，令

dp_{i,j}

表示第

i

行，第

j

列，最多能向上拓展几个

1

。易得，

dp_{i,j} = \begin{cases} dp_{i-1,j} + 1 & a_{i,j} = 1 \\ 0 & a_{i,j} = 0 \end{cases}

得到此数组后，开始下一步。

解决

发现自右向左维护一个严格单调递增的栈（存下标）比较方便。

对于每一个新加入的数，若比栈顶元素大，放入，否则不断弹出直到栈为空或比栈顶元素大。此时，若栈为空，则它为最小值，那么新更新的就是长为

m-j+1

，宽为

dp_{i,j}

的矩阵。若栈不为空，则更新的矩形为长为

(s_{top}-j)

，宽为

dp_{i,j}

的矩形。

代码

CPP

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#define int long long
#define N 4000005
using namespace std;
inline void read(int &x){
	int f=1; x=0; char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	x*=f;
}
inline void write(long long x){
	if(x<0)
		putchar('-'),x=-x;
	if(x>=10)
		write(x/10);
	putchar(x%10+'0');
}
int n,m;
vector<int> a[N],dp[N];
int s[N],top,f[N];
int fans;
signed main(){
	read(n); read(m);
	for(int i=0;i<=n+1;i++)
		a[i].resize(m+1),dp[i].resize(m+1);
	for(int i=1;i<=n;i++){
		string s; cin>>s; s=' '+s;
		for(int j=1;j<=m;j++)
			a[i][j]=s[j]-'0';
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]==1)
				dp[i][j]=dp[i-1][j]+1;
	s[0]=m;//记得初始化
	for(int i=1;i<=n;i++){
		top=0;//清空
		int res=0,ans=0;
		for(int j=m;j>=1;j--){
			while(dp[i][j]<=dp[i][s[top]]&&top)
				top--;//小于就弹出
			if(top)//不为空
				f[j]=f[s[top]]+(s[top]-j)*dp[i][j];//可续接
			else//为空
				f[j]=(m-j+1)*dp[i][j];
			s[++top]=j;//加入
			ans=max(ans,f[j]);//更新
		}
		fans=max(fans,ans);
	}
	write(fans);
	return 0;
}

后记

听说考前发题解会 ++RP。求过。

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

文章操作

分析

解决

代码

后记

相关推荐

评论

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