比赛 |
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;
}