比赛 2022级DP专题练习赛5 评测结果 AAAAAAAAAA
题目名称 Sue的小球 最终得分 100
用户昵称 yrtiop 运行时间 0.001 s
代码语言 C++ 内存使用 1.34 MiB
提交时间 2023-02-22 20:02:20
显示代码纯文本
#include <bits/stdc++.h>
using i64 = long long;

const int maxn = 1e3 + 5;
struct node {
	int x,y,v;
	node() {
		x = y = v = 0;
	}
	node(int x,int y,int v):x(x),y(y),v(v){}
}a[maxn];
int n,x,f[maxn][maxn][2],sum[maxn];

int main() {
	freopen("sueball.in","r",stdin);
	freopen("sueball.out","w",stdout);
	scanf("%d %d",&n,&x);
	for(int i = 1;i <= n;++ i)
		scanf("%d",&a[i].x);
	for(int i = 1;i <= n;++ i)
		scanf("%d",&a[i].y);
	for(int i = 1;i <= n;++ i)
		scanf("%d",&a[i].v);
	std::sort(a + 1 , a + 1 + n , [&](const node& p,const node& q) {
		return p.x < q.x;
	});
	for(int i = 1;i <= n;++ i)
		sum[i] = sum[i - 1] + a[i].v;
	int ans = 0;
	for(int i = 1;i <= n;++ i)
		ans += a[i].y;
	for(int i = 1;i <= n;++ i)
		f[i][i][0] = f[i][i][1] = sum[n] * std::abs(a[i].x - x);
	for(int len = 2;len <= n;++ len) {
		for(int i = 1;i + len - 1 <= n;++ i) {
			int j = i + len - 1;
			f[i][j][0] = std::min(f[i + 1][j][0] + std::abs(a[i + 1].x - a[i].x) * (sum[n] - (sum[j] - sum[i])) ,
				f[i + 1][j][1] + std::abs(a[j].x - a[i].x) * (sum[n] - (sum[j] - sum[i])));
			f[i][j][1] = std::min(f[i][j - 1][0] + std::abs(a[i].x - a[j].x) * (sum[n] - (sum[j - 1] - sum[i - 1])) ,
				f[i][j - 1][1] + std::abs(a[j - 1].x - a[j].x) * (sum[n] - (sum[j - 1] - sum[i - 1])));
		}
	}
	printf("%.3lf\n",(ans - std::min(f[1][n][0] , f[1][n][1])) / 1000.0);
	return 0;
}