记录编号	452608	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
题目名称	有趣的有趣的家庭菜园	最终得分	33
用户昵称	Shirry	是否通过	未通过
代码语言	C++	运行时间	60.706 s
提交时间	2017-09-19 21:25:34	内存使用	0.45 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5010;
struct poi{
	int h,p,c;
}a[maxn];
int n;
long long ans,L[maxn],R[maxn];
void dfs1(int x,int h,long long num){
	if(x==n+1){ans=max(ans,num);return;}
	int t=h;
	long long p=num;
	h=max(h,a[x].h);//do not pull up
	if(h<=a[x].h)num=num+a[x].p;
	L[x]=max(L[x],num);
	dfs1(x+1,h,num);
	num=p-a[x].c;//pull up
	L[x]=max(L[x],num);
	dfs1(x+1,t,num);
}
void dfs2(int x,int h,long long num){
	if(x==0){ans=max(ans,num);return;}
	int t=h;
	long long p=num;
	R[x]=max(R[x],num);
	h=max(h,a[x].h);//do not pull up
	if(h<=a[x].h)num=num+a[x].p;
	dfs2(x-1,h,num);
	num=p-a[x].c;//pull up 
	dfs2(x-1,t,num);
}
int main(){
	freopen("Fgarden.in","r",stdin);
	freopen("Fgarden.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].h,&a[i].p,&a[i].c);
	dfs1(1,0,0);
	dfs2(n,0,0);
	for(int i=1;i<=n;i++)ans=max(ans,L[i]+R[i]);
	printf("%lld",ans);
	return 0;
}