10pts AC on #11求条

//P2466 [SDOI2008] Sue 的小球 
//难度：蓝  解法：区间dp 
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,v;
}a[1010];
long long n,x0;
long long dp[1010][1010][2];
long long t[1010][1010][2];
bool cmp(node x,node y){
	return x.x<y.x;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(t,0xff,sizeof(t));
	cin>>n>>x0;
	for(int i=1;i<=n;i++){
		cin>>a[i].x;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i].y;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i].v;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		t[i][i][0]=abs(x0-a[i].x);
		t[i][i][1]=abs(x0-a[i].x);
		dp[i][i][0]=a[i].y-t[i][i][0]*a[i].v;
		dp[i][i][1]=a[i].y-t[i][i][1]*a[i].v;
	}
	for(int len=2;len<=n;len++){
		for(int l=1;l<=n-len+1;l++){
			int r=l+len-1;
			t[l][r][0]=min(t[l+1][r][0]+abs(a[l+1].x-a[l].x),t[l+1][r][1]+abs(a[r].x-a[l].x));
			t[l][r][1]=min(t[l][r-1][0]+abs(a[l].x-a[r].x),t[l][r-1][1]+abs(a[r-1].x-a[r].x));
			dp[l][r][0]=dp[l+1][r][0]+(a[l].y-t[l][r][0]*a[l].v);
			dp[l][r][1]=dp[l][r-1][0]+(a[r].y-t[l][r][1]*a[r].v);
			
		}
	}
	printf("%.3f",max(dp[1][n][0],dp[1][n][1])*0.001);
}
/*
是否可能 时间更长但路程更短？不可能 
*/