题目大意
Sue和Sandy最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上，Sue有一支轻便小巧的小船。然而，Sue的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋，Sue有一个秘密武器，只要她将小船划到一个彩蛋的正下方，然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而，彩蛋有一个魅力值，这个魅力值会随着彩蛋在空中降落的时间而降低，Sue要想得到更多的分数，必须尽量在魅力值高的时候收集这个彩蛋，而如果一个彩蛋掉入海中，它的魅力值将会变成一个负数，但这并不影响Sue的兴趣，因为每一个彩蛋都是不同的，Sue希望收集到所有的彩蛋。
然而Sandy就没有Sue那么浪漫了，Sandy希望得到尽可能多的分数，为了解决这个问题，他先将这个游戏抽象成了如下模型：
以Sue的初始位置所在水平面作为$x$轴。
一开始空中有$N$个彩蛋，对于第$i$个彩蛋，他的初始位置用整数坐标$(x_i,y_i)$表示，游戏开始后，它匀速沿$y$轴负方向下落,速度为$v_i$单位距离/单位时间。Sue的初始位置为$(x_0,0)$，Sue可以沿$x$轴的正方向或负方向移动，Sue的移动速度是$1$单位距离/单位时间，使用秘密武器得到一个彩蛋是瞬间的，得分为当前彩蛋的$y$坐标的千分之一。
现在，Sue和Sandy请你来帮忙，为了满足Sue和Sandy各自的目标，你决定在收集到所有彩蛋的基础上，得到的分数最高。
题目分析
和关路灯类似的区间Dp。
设$f[i,j,0/1]$表示将区间$[i,j]$的彩蛋全部收集，所得到的最高分数。
转移和关路灯几乎一样。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1005;
struct Egg {
int x,y;
LL v;
bool operator < (const Egg& b) const {
return x<b.x||(x==b.x&&y<b.y);
}
} a[maxn];
int n,x0;
LL f[maxn][maxn][2],sum[maxn];
int main() {
n=Get_Int();
x0=Get_Int();
for(int i=1; i<=n; i++)a[i].x=Get_Int();
for(int i=1; i<=n; i++)a[i].y=Get_Int();
for(int i=1; i<=n; i++)a[i].v=Get_Int();
sort(a+1,a+n+1);
for(int i=1; i<=n; i++)sum[i]=sum[i-1]+a[i].v;
for(int i=1; i<=n; i++)f[i][i][0]=f[i][i][1]=a[i].y-abs(x0-a[i].x)*sum[n];
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]=f[i][j][1]=-1e18;
f[i][j][0]=max(f[i][j][0],f[i+1][j][1]+a[i].y-abs(a[j].x-a[i].x)*(sum[n]-sum[j]+sum[i]));
f[i][j][0]=max(f[i][j][0],f[i+1][j][0]+a[i].y-abs(a[i+1].x-a[i].x)*(sum[n]-sum[j]+sum[i]));
f[i][j][1]=max(f[i][j][1],f[i][j-1][0]+a[j].y-abs(a[j].x-a[i].x)*(sum[n]-sum[j-1]+sum[i-1]));
f[i][j][1]=max(f[i][j][1],f[i][j-1][1]+a[j].y-abs(a[j].x-a[j-1].x)*(sum[n]-sum[j-1]+sum[i-1]));
}
printf("%0.3lf\n",max(f[1][n][0],f[1][n][1])/1000.0);
return 0;
}
|
