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