区间 DP ，和这个在我看来一模一样。

AC on #2 #3 #11

#include <bits/stdc++.h>
#pragma GCC optmize(2)
#define debug puts("done")
using namespace std;

#define int long long
int n,x0;
int x[1005],y[1005],v[1005];
int dp[1005][1005][3];

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>x0;
	for(int i=1;i<=n;i++) cin>>x[i];
	for(int i=1;i<=n;i++) cin>>y[i];
	for(int i=1;i<=n;i++) cin>>v[i],v[i]+=v[i-1];
	sort(x+1,x+n+1);
	for(int i=1;i<=n;i++) dp[i][i][1]=dp[i][i][2]=y[i]-abs(x[i]-x0)*v[n],cout<<dp[i][i][1]<<endl;
	for(int l=2;l<=n;l++)
		for(int i=1;i+l-1<=n;i++){
			int j=i+l-1;
			dp[i][j][1]=max(dp[i+1][j][1]-(x[i+1]-x[i])*(v[n]-v[j]+v[i]),dp[i+1][j][2]-(x[j]-x[i])*(v[n]-v[j]+v[i]))+y[i];
			dp[i][j][2]=max(dp[i][j-1][2]-(x[j]-x[j-1])*(v[n]-v[j-1]+v[i-1]),dp[i][j-1][1]-(x[j]-x[i])*(v[n]-v[j-1]+v[i-1]))+y[j];
		}
	printf("%.3lf",max(dp[1][n][1],dp[1][n][2])/1000.0);
	return 0;
}