比赛 2022级DP专题练习赛5 评测结果 AAAAAAAAAA
题目名称 Sue的小球 最终得分 100
用户昵称 HeSn 运行时间 0.025 s
代码语言 C++ 内存使用 12.79 MiB
提交时间 2023-02-22 20:51:08
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, st, f[2][1010][1010];
struct node {
	int x, y, v;
}a[1010];
bool cmp(node x, node y) {
	return x.x < y.x;
}
signed main() {
	freopen("sueball.in", "r", stdin);
	freopen("sueball.out", "w", stdout);
	cin >> n >> st;
	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;
	} 
	a[n + 1].x = st;
	n ++;
	sort(a + 1, a + n + 1, cmp);
	int pos, sum = 0;
	for(int i = 1; i <= n; i ++) {
		sum += a[i].y;
		a[i].v += a[i - 1].v;
	}
	memset(f, 0x3f, sizeof(f));
	for(int i = 1; i <= n; i ++) {
		if(st == a[i].x) {
			pos = i;
			f[0][i][i] = f[1][i][i] = 0;
			break;
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1, k = j + i; k <= n; j ++, k ++) {
			f[0][j][k] = min(f[0][j + 1][k] + (a[j + 1].x - a[j].x) * (a[j].v + a[n].v - a[k].v),
							 f[1][j + 1][k] + (a[k].x - a[j].x) * (a[j].v + a[n].v - a[k].v));
			f[1][j][k] = min(f[0][j][k - 1] + (a[k].x - a[j].x) * (a[j - 1].v + a[n].v - a[k - 1].v),
							 f[1][j][k - 1] + (a[k].x - a[k - 1].x) * (a[j - 1].v + a[n].v - a[k - 1].v));
		} 
	}
	printf("%0.3f", (sum - min(f[0][1][n], f[1][1][n])) / 1000.0);
	return 0;
}