POJ 2559 Largest Rectangle in a Histogram —— 笛卡尔树模板

本文主要是介绍POJ 2559 Largest Rectangle in a Histogram —— 笛卡尔树模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有n个连着的矩形，每个矩形的宽为1，高为a[i]，问你在这些矩形内部最大能组成的矩形大小。

题解：

笛卡尔树模板，模板和之前有了一些变化，增加了连边的特判，这样子就算有起始点为0的地方也无妨。当然要注意初始化

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
int fa[N],ls[N],rs[N],st[N],top;
int n;
ll a[N];
void build(){top=0;for(int i=1;i<=n;i++){ls[i]=rs[i]=fa[i]=0;int f=0;while(top&&a[st[top]]>a[i])top--,f=1;if(top)fa[i]=st[top],rs[st[top]]=i;if(f)ls[i]=st[top+1],fa[ls[i]]=i;st[++top]=i;}
}
ll ans;
void dfs(int l,int r,int root){//if(l>r)return ;ans=max(ans,a[root]*(r-l+1));if(ls[root])dfs(l,root-1,ls[root]);if(rs[root])dfs(root+1,r,rs[root]);
}
int main()
{while(~scanf("%d",&n)){if(!n)break;for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build();ans=0;dfs(1,n,st[1]);printf("%lld\n",ans);}return 0;
}

这篇关于POJ 2559 Largest Rectangle in a Histogram —— 笛卡尔树模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---