比赛 |
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;
}