90Wa#11?
查看原帖
90Wa#11?
483090
yeahhhhhh楼主2024/2/29 14:02
#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N=1e3+5;
int st;
int sum[N];
struct node {
	int x,y,v;
} egg[N];
long long  dp1[2*N][2*N],dp2[2*N][2*N];
long long all;
bool cmp(node a,node b) {
	return a.x<b.x;
}
int n;
signed main() {
	cin>>n>>st;
	for(int i=1; i<=n+2; i++) {
		for(int j=1; j<=n+2; j++) {
			dp1[i][j]=(int)1e18;
			dp2[i][j]=(int)1e18;
		}
	}
	for(int i=1; i<=n; i++) {
		cin>>egg[i].x;
	}
	for(int i=1; i<=n; i++) {
		cin>>egg[i].y;
		all+=egg[i].y;
	}
	for(int i=1; i<=n; i++) {
		cin>>egg[i].v;
	}
	egg[++n].x=st;
	sort(egg+1,egg+1+n,cmp);
	for(int i=1; i<=n; i++) {
		sum[i]=egg[i].v+sum[i-1];
	}
	for(int i=1; i<=n; i++) {
		if(egg[i].x==st&&egg[i].v==0) {
			dp1[i][i]=dp2[i][i]=0;
			break;
		}

	}

	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+1][j]+(egg[i+1].x-egg[i].x)*(sum[i]+sum[n]-sum[j]),
			              dp2[i+1][j]+(egg[j].x-egg[i].x)*(sum[i]+sum[n]-sum[j]));
			dp2[i][j]=min(dp2[i][j-1]+(egg[j].x-egg[j-1].x)*(sum[n]+sum[i-1]-sum[j-1]),
			              dp1[i][j-1]+(egg[j].x-egg[i].x)*(sum[n]-sum[j-1]+sum[i-1]));
		}
	}
	printf("%.3lf",(all-min(dp2[1][n],dp1[1][n]))*1.0/1000);
	return 0;
}
2024/2/29 14:02
加载中...