比赛 |
20151028a |
评测结果 |
WWWWWWWWWWAWAWAWWWWWWWAWWWWWAWWWWAWWWWWWWAWWWWWTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
题目名称 |
有趣的有趣的家庭菜园 |
最终得分 |
7 |
用户昵称 |
mikumikumi |
运行时间 |
44.171 s |
代码语言 |
C++ |
内存使用 |
1.76 MiB |
提交时间 |
2015-10-28 10:30:25 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int SIZEN=100010;
int N;
int H[SIZEN]={0},P[SIZEN]={0},C[SIZEN]={0};
int val[SIZEN];
void read()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%d%d%d",&H[i],&P[i],&C[i]);
}
}
void work()
{
int ans=0;
int f[SIZEN];
memset(f,0,sizeof(f));
for(int i=1;i<=N;i++)
{
int ma=0;
for(int j=0;j<i;j++)
{
int tem=0;
if(H[j]<H[i])
{
int now=H[j];
for(int k=j+1;k<=i-1;k++)
{
if(H[k]>now) tem-=C[k];
}
tem+=f[j];
tem+=P[i];
ma=max(tem,ma);
}
}
f[i]=ma;
}
for(int i=1;i<=N;i++) val[i]=f[i];
//for(int i=1;i<=N;i++) cout<<val[i]<<endl;
memset(f,0,sizeof(f));
for(int i=N;i>=1;i--)
{
int ma=0;
for(int j=N+1;j>i;j--)
{
int tem=0;
if(H[j]<H[i])
{
int now=H[j];
for(int k=i+1;k<=j-1;k++)
{
if(H[k]>now) tem-=C[k];
}
tem+=f[j];
tem+=P[i];
ma=max(tem,ma);
}
}
f[i]=ma;
}
for(int i=1;i<=N;i++)
{
val[i]+=(f[i]-P[i]);
ans=max(val[i],ans);
}
printf("%d",ans);
}
int main()
{
freopen("Fgarden.in","r",stdin);
freopen("Fgarden.out","w",stdout);
read();
work();
return 0;
}