#4019. 有趣的有趣的家庭菜园（garden）

81 阅读 0 评论 54 点赞

我是靠谱客的博主羞涩西牛，最近开发中收集的这篇文章主要介绍#4019. 有趣的有趣的家庭菜园（garden），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

职业经营家庭菜园的JOI君每年在自家的田地中种植一种叫做IOI草的植物。IOI草的种子在冬天被播下，春天会发芽并生长至一个固定的高度。到了秋天，一些IOI草会结出美丽的果实，并被收获，其他的IOI草则会在冬天枯萎。

JOI君的田地沿东西方向被划分为NNN个区域，从西侧开始的第iii个区域中种植着IOI草iii。在第iii个区域种植的IOI草，在春天的时候高度会生长至HiH_iHi，此后便不再生长。如果IOI草iii会结出果实，那么将会获得PiP_iPi的收益，否则没有收益。

春天到了，查看田地样子的JOI君决定拔掉一些种植的IOI草，使利益最大化。拔掉IOI草iii需要CiC_iCi的花销，拔掉的IOI草会立刻枯萎。IOI草只能在春天被拔掉，夏天和秋天不能拔掉IOI草。

IOI草是一种非常依靠阳光的植物，如果在夏天某个区域的IOI草的东侧和西侧都有比它高的IOI草存在，那么这株IOI草在秋天便不会结出果实。换句话说，为了让没有被拔掉的IOI草iii在秋天结出果实，到了夏天的时候，以下两个条件至少满足一个：

1.对于任意1<=j<=i−11<=j<=i-11<=j<=i−1，Hj≤HiH_jleq H_iHj≤Hi或IOI草jjj已经被拔除

2.对于任意i+1<=j<=Ni+1<=j<=Ni+1<=j<=N，Hj≤HiH_jleq H_iHj≤Hi或IOI草jjj已经被拔除

用最终收获的果实的总价格减掉拔除IOI草的花销的总和，即为JOI君的收益。那么JOI君能从IOI草中获取的最大利益到底有多少呢？
输入格式

第一行一个正整数NNN，表示田地被分为了NNN个区域。

接下来NNN行，第iii行(1<=i<=N)(1<=i<=N)(1<=i<=N)三个空白分割的正整数Hi,Pi,CiH_i,P_i,C_iHi,Pi,Ci，表示第iii株IOI草在春天时高度会生长至HiH_iHi，秋天收获的果实的价格为PiP_iPi，拔除所需费用为CiC_iCi。
输出格式

输出一行一个整数，表示JOI君能获得的最大利益。
样例
样例输入

7
22 60 30
46 40 30
36 100 50
11 140 120
38 120 20
24 90 60
53 50 20

样例输出

320

数据范围与提示

【样例解释】

拔除IOI草2和IOI草7，剩余的IOI草如下图所示：

IOI草1、3、5、6的果实价格分别为60、100、120、90，拔除IOI草2和IOI草7的花销分别为30、20，总收益为320，这是所有方案中的最大值。

【数据范围与约定】

对于30%30%30%的数据，N≤20Nleq 20N≤20。

对于45%45%45%的数据，N≤300Nleq 300N≤300。

对于60%60%60%的数据，N≤5000Nleq 5000N≤5000。

对于100%100%100%的数据，3≤N≤105,1≤Hi≤109(1≤i≤N),1≤Pi≤109(1≤i≤N),1≤Ci≤109(1≤i≤N)3leq Nleq 10^5,1leq H_ileq 10^9(1leq ileq N),1leq P_ileq 10^9(1leq ileq N),1leq C_ileq 10^9(1leq ileq N)3≤N≤105,1≤Hi≤109(1≤i≤N),1≤Pi≤109(1≤i≤N),1≤Ci≤109(1≤i≤N)。
来源

JOI camp 2015

题解：
由题意可得，必有一株IOI草是最高的，且所以该草左右都只有三种选择
①要么被砍
②要么没有影响
③要么左或右都比它矮
所以我们可以定
f[i]表示该草左边都不高于它时的最大总收益。
f[i]=max(f[j]-sigma(c[k])(j<k<i&&h[k]>h[i]))(h[j]<=h[i]);
右边同理

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100005
using namespace std;
long long n,lf[N],rf[N],c[N],p[N],h[N],b[N],pre[N];
struct segmentree
{
	int l,r;
	long long maxn,lazy;
}t[N*4];
int tot;
void discrete()
{
	sort(b+1,b+1+n);
	tot=unique(b+1,b+1+n)-b-1;
}
inline long long raw(long long h){
	return lower_bound(b+1,b+1+tot,h)-b;
}
void build(int p,int l,int r){
	t[p].l=l;t[p].r=r;t[p].maxn=0;
	if(l==r){t[p].maxn=0;return ;}
	int mid=(l+r)>>1;
	build(p*2,l,mid);build(p*2+1,mid+1,r);
	
}
void spread(int p){
	if(t[p].lazy){
		t[p*2].maxn+=t[p].lazy;
		t[p*2+1].maxn+=t[p].lazy;
		t[p*2].lazy+=t[p].lazy;
		t[p*2+1].lazy+=t[p].lazy;
		t[p].lazy=0;
	}
}
void add(int p,int l,int r,long long val){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].maxn+=val;
		t[p].lazy+=val;
	    return ;
	}
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)add(p*2,l,r,val);
	if(r>mid)add(p*2+1,l,r,val);
    t[p].maxn=max(t[p*2].maxn,t[p*2+1].maxn);
}
void reset(int p,int l,long long val){
	if(t[p].l==t[p].r){
		t[p].maxn=max(t[p].maxn,val);
		return ;
	}
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)reset(p*2,l,val);
	if(l>mid)reset(p*2+1,l,val);
	t[p].maxn=max(t[p*2].maxn,t[p*2+1].maxn);
}
long long ask(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r){
		return t[p].maxn;
	}
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	long long maxn=-1e16;
	if(l<=mid)maxn=max(maxn,ask(p*2,l,r));
	if(r>mid)maxn=max(maxn,ask(p*2+1,l,r));
	return maxn;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i]>>p[i]>>c[i];
	    b[i]=h[i];
	}
	discrete();
	build(1,0,tot);
	lf[0]=0;reset(1,0,0);
	for(int i=1;i<=n;i++){
		int x=raw(h[i]);
		long long maxn=ask(1,0,x);
		lf[i]=maxn+p[i];
		add(1,0,x-1,-c[i]);
		reset(1,x,lf[i]);
	}
	rf[0]=rf[n+1]=0;build(1,0,tot);
	reset(1,0,0);
	for(int i=n;i>=1;i--){
		int x=raw(h[i]);
		long long maxn=ask(1,0,x);
		rf[i]=maxn+p[i];
		add(1,0,x-1,-c[i]);
		reset(1,x,rf[i]);
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,lf[i]+rf[i]-p[i]);
	}
	//for(int i=1;i<=n;i++)cout<<lf[i]<<" ";cout<<endl;
	//for(int i=1;i<=n;i++)cout<<rf[i]<<" ";cout<<endl;
	cout<<ans<<endl;
	return 0;
}
		
/*
7
22 60 30
46 40 30
36 100 50
11 140 120
38 120 20
24 90 60
53 50 20
*/