比赛 20151028a 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
题目名称 有趣的有趣的家庭菜园 最终得分 33
用户昵称 Shirry 运行时间 60.683 s
代码语言 C++ 内存使用 0.45 MiB
提交时间 2017-09-19 21:26:05
显示代码纯文本
#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;
}