记录编号	306591	评测结果	AAAAAAAAAA
题目名称	[SDOI 2008]Sue的小球	最终得分	100
用户昵称	iortheir	是否通过	通过
代码语言	C++	运行时间	0.114 s
提交时间	2016-09-12 17:53:12	内存使用	18.81 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

const int maxn=1000+100;

struct T
{
	double x;
	double y;
	double v;
}A[maxn];

int n;
double x0;
double sum[maxn];
double f[maxn][maxn][2];

inline double comp(const T& a,const T& b)
{
	return a.x<b.x;
}

int main()
{
	freopen("sueball.in","r",stdin);
	freopen("sueball.out","w",stdout);
	scanf("%d%lf",&n,&x0);
	for(int i=1;i<=n;++i){scanf("%lf",&A[i].x);}
	for(int i=1;i<=n;++i){scanf("%lf",&A[i].y);}
	for(int i=1;i<=n;++i){scanf("%lf",&A[i].v);}
	sort(A+1,A+1+n,comp);
	for(int i=1;i<=n;++i){sum[i]=sum[i-1]+A[i].v;}//提前把所有下落小球所损失的费用计算好
	//sum[n]则为所有小球下降一秒的费用
	for(int i=1;i<=n;++i){f[i][i][0]=f[i][i][1]=A[i].y-sum[n]*abs(A[i].x-x0);}//yi-t*sum[i];
	//当前所得到的y值减去除此处外所有下降气球的费用为最终获得值
	for(int k=2;k<=n;++k)
	{
		for(int i=1;i<=n-k+1;++i)
		{
			int j=i+k-1;
			f[i][j][0]=max(f[i+1][j][0]+A[i].y-(abs(A[i].x-A[i+1].x)*(sum[i]+sum[n]-sum[j])),f[i+1][j][1]+A[i].y-(abs(A[i].x-A[j].x)*(sum[i]+sum[n]-sum[j])));
			f[i][j][1]=max(f[i][j-1][1]+A[j].y-(abs(A[j].x-A[j-1].x)*(sum[i-1]+sum[n]-sum[j-1])),f[i][j-1][0]+A[j].y-(abs(A[j].x-A[i].x)*(sum[i-1]+sum[n]-sum[j-1])));
		}
	}
	double ans=(1.0*max(f[1][n][0],f[1][n][1]))/1000.0;
	printf("%.3lf\n",ans);
	return 0;
}