关于机器猫大战唐僧这件事

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e3+10;
ll dp1[MAXN][MAXN]; //l->r->l
ll dp2[MAXN][MAXN]; //l->r
ll sum[MAXN];
int n,start;
ll tmp;

struct node{
	int x,y,v;
}egg[MAXN];

bool cmp(node a,node b){
	return a.x<b.x;
}

ll calc(int l,int r){
	return sum[r]-sum[l-1];
}

int main(){
	memset(dp1,0x3f,sizeof(dp1));
	memset(dp2,0x3f,sizeof(dp2));
	scanf("%d%d",&n,&start);
	for(int i=1;i<=n;++i)
		scanf("%d",&egg[i].x);
	for(int i=1;i<=n;++i){
		scanf("%d",&egg[i].y);
		tmp+=egg[i].y;
	}
	for(int i=1;i<=n;++i)
		scanf("%d",&egg[i].v);
	egg[++n].x=start;
	sort(egg+1,egg+n+1,cmp);
	
	for(int i=1;i<=n;++i){
		sum[i]=sum[i-1]+egg[i].v;
		if(egg[i].x==start&&egg[i].v==0){
			dp1[i][i]=dp2[i][i]=0;
		}
	} 
	
	for(int len=2;len<=n;++len){
		for(int i=1;i<=n-len+1;++i){
			int j=i+len-1;
			dp1[i][j]=min(dp1[i][j],dp1[i+1][j]+(egg[i+1].x-egg[i].x)*(calc(1,i)+calc(j+1,n)));
			dp1[i][j]=min(dp1[i][j],dp2[i+1][j]+(egg[j].x-egg[i].x)*(calc(1,i)+calc(j+1,n)));
			dp2[i][j]=min(dp2[i][j],dp1[i][j-1]+(egg[j].x-egg[i].x)*(calc(1,i-1)+calc(j,n)));
			dp2[i][j]=min(dp2[i][j],dp2[i][j-1]+(egg[j-1].x-egg[j].x)*(calc(1,i-1)+calc(j,n)));
		}
	}
	tmp=tmp-min(dp1[1][n],dp2[1][n]);
	printf("%.3lf",tmp/1000.0);
	return 0;
}