比赛 20151028a 评测结果 AWAWWWWWWWWWWAAWWWWWWWWWWAWWWWWWWAWWWWWWWAWWWWWWWWWWWAWWWWWWWTWTTWTTTWTTWWTWWTWWTWTWTTTWTW
题目名称 有趣的有趣的家庭菜园 最终得分 8
用户昵称 农场主 运行时间 17.192 s
代码语言 C++ 内存使用 2.96 MiB
提交时间 2015-10-28 12:13:36
显示代码纯文本
#include<cstdio>
using namespace std;
class v
{
public:
	int x,h;
}l[100010]={0},r[100010]={0};
int H[100010]={0},P[100010]={0},C[100010]={0};
int main()
{
	freopen("Fgarden.in","r",stdin);
	freopen("Fgarden.out","w",stdout);
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d%d%d",&H[i],&P[i],&C[i]);
	for (int i=1;i<=n;i++)
	{
		int j=i-1,sum=0;
		while (H[i]<l[j].h){sum+=P[j]+C[j];j--;}
		if (l[j].x+sum<l[i-1].x+P[i])
		{
			l[i].x=l[j].x+sum;
			l[i].h=H[i];
		}//选这个点
		else
		{
			l[i].x=l[i-1].x+P[i];
			l[i].h=l[i-1].h;
		}//不选这个点
	}
	H[n+1]=199999999;
	for (int i=n;i>=1;i--)
	{
		int j=i+1,sum=0;
		while (H[i]<r[j].h){sum+=P[j]+C[j];j++;}
		if (r[j].x+sum<r[i+1].x+P[i])
		{
			r[i].x=r[j].x+sum;
			r[i].h=H[i];
		}//选这个点
		else
		{
			r[i].x=r[i+1].x+P[i];
			r[i].h=r[i+1].h;
		}//不选这个点
	}
	int max=199999999;
	for (int i=2;i<=n-1;i++)
	{
		if(max>r[i].x+l[i+1].x)max=r[i].x+l[i+1].x;
		if(max>r[i+1].x+l[i].x)max=r[i+1].x+l[i].x;
	}
	long long ans=0;
	for (int i=1;i<=n;i++) ans+=P[i];
	ans-=max;
	printf("%d",ans);
}