记录编号	87155	评测结果	AAAAAAAAAA
题目名称	[SDOI 2008]Sue的小球	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.069 s
提交时间	2014-02-01 19:20:02	内存使用	10.06 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
using namespace std;
const int SIZEN=1010,INF=0x7fffffff/2;
int N,X0;
int startpos;
int totY=0;
pair<int,int> balls[SIZEN];//x坐标和速度
int preV[SIZEN]={0};
int f1[SIZEN][SIZEN]={0},f2[SIZEN][SIZEN]={0};
//f1是在左端,f2是在右端
bool vis1[SIZEN][SIZEN]={0},vis2[SIZEN][SIZEN]={0};
inline int W(int x,int y){//除了区间[x,y]的所有速度和
	return preV[N]-(preV[y]-preV[x-1]);
}
int DP1(int,int);
int DP2(int,int);
int DP1(int x,int y){//计算f1
	if(balls[x].first>X0||balls[y].first<X0) return INF;//这样的情况在最优移动中是不可能出现的
	if(vis1[x][y]) return f1[x][y];
	vis1[x][y]=true;
	if(x==y) return f1[x][y]=0;
	f1[x][y]=INF;
	f1[x][y]=min(f1[x][y],DP2(x+1,y)+(balls[y].first-balls[x].first)*W(x+1,y));
	f1[x][y]=min(f1[x][y],DP1(x+1,y)+(balls[x+1].first-balls[x].first)*W(x+1,y));
	return f1[x][y];
}
int DP2(int x,int y){//计算f2
	if(balls[x].first>X0||balls[y].first<X0) return INF;//这样的情况在最优移动中是不可能出现的
	if(vis2[x][y]) return f2[x][y];
	vis2[x][y]=true;
	if(x==y) return f2[x][y]=0;//一定收敛到初始位置
	f2[x][y]=INF;
	f2[x][y]=min(f2[x][y],DP2(x,y-1)+(balls[y].first-balls[y-1].first)*W(x,y-1));
	f2[x][y]=min(f2[x][y],DP1(x,y-1)+(balls[y].first-balls[x].first)*W(x,y-1));
	return f2[x][y];
}
void read(void){
	scanf("%d%d",&N,&X0);
	for(int i=1;i<=N;i++) scanf("%d",&balls[i].first);
	int y;
	for(int i=1;i<=N;i++) scanf("%d",&y),totY+=y;
	for(int i=1;i<=N;i++) scanf("%d",&balls[i].second);
	N++;
	balls[N]=make_pair(X0,0);//为了简化问题,设一个起点立刻能接到的小球,其得分为0(totY不改变),速度为0
}
int main(){
	freopen("sueball.in","r",stdin);
	freopen("sueball.out","w",stdout);
	read();
	sort(balls+1,balls+1+N);
	for(int i=1;i<=N;i++) preV[i]=preV[i-1]+balls[i].second;
	int numdec=min(DP1(1,N),DP2(1,N));
	double ans=(totY-numdec+0.0)/1000.0;
	printf("%.3lf\n",ans);
	return 0;
}