• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

L – Two Buildings(决策单调性分治 )2020-2021 ACM-ICPC Asia Seoul Regional Contest

开发技术 开发技术 2周前 (05-04) 4次浏览

L – Two Buildings

题意:给水平上n条垂线的长度,选择其中两条线围成梯形,求出最大的梯形面积。

题解:首先贪心分析一下,要使面积最大,尽量使高(两条线水平距离)和两底(两条线长度)更大,所以我们可以先预处理出两组线,一组表示取出来放在左边的线,一组表示放在右边的线。

我们分析一下从左边取出一条怎样的线才是好的。

第一,它应该要靠左,这样可以使高更大。

第二,它长度应该长,这样可以使底更长。

对于靠右且长度还没其他边长的边就应该去除,这里我们可以用单调栈处理(右边同理)。

现在我们再考虑暴力加剪枝的方法写这个题。

我们算左边的线某条线now的贡献,暴力找到右边使面积最大的线p。

对于now来说,p-1的线高不够,p+1的线底不够。

那么对于now+1来说, p-1的贡献也必然不如p,因为我缺的是高,给我更长一点的底没有意义。

对于now-1,同理。

所以对于比now大的边,我没有必要再查比p小的边了,比now小的边,也没必要查比p大的边了。

这里就可以用分治解决了,时间复杂度类似于快速排序,但不会被特殊样例卡时间,因为对于左边的线l至r每次稳定减半。

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define ll long long
const ll N=1e6+7;
ll n,a[N],ans;
stack<ll>sa;
vector<ll>ho,aq;
ll cal(ll x,ll y){
	ll p=aq[x];
	ll P=ho[y];
	return (P-p)*(a[P]+a[p]);
}
void gao(ll l,ll r,ll L,ll R){
	if(l>r){
		return;
	}
	ll mid=(l+r)/2;
	ll p=L;
	for(int i=L;i<=R;i++){
		if(cal(mid,p)<cal(mid,i)){
			p=i;
		}
	}
	ans=max(ans,cal(mid,p));
	gao(l,mid-1,L,p);
	gao(mid+1,r,p,R);
}
int main(){
	ho.push_back(0);
	aq.push_back(0);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
		while(!sa.empty()){
			ll p=sa.top();
			if(a[p]<=a[i]){
				sa.pop();
			}
			else{
				break;
			}
		}
		sa.push(i);
	}
	while(!sa.empty()){
		ho.push_back(sa.top());
		sa.pop();
	}
	for(int i=n;i>=1;i--){
		while(!sa.empty()){
			ll p=sa.top();
			if(a[p]<=a[i]){
				sa.pop();
			}
			else{
				break;
			}
		}
		sa.push(i);
	}
	while(!sa.empty()){
		aq.push_back(sa.top());
		sa.pop();
	}
	sort(ho.begin(),ho.end());
	sort(aq.begin(),aq.end());
	gao(1,aq.size()-1,1,ho.size()-1);
	printf("%lldn",ans);
}

喜欢 (0)