三、Sue 的小球
(ball.pas/c/cpp，限时0.5 秒，内存256M)
【题目描述】
Sue 和Sandy 最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺
激的大海上，Sue 有一支轻便小巧的小船。然而，Sue 的目标并不是当一个海盗，而是
要收集空中漂浮的彩蛋，Sue 有一个秘密武器，只要她将小船划到一个彩蛋的正下方，
然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而，彩蛋有一个魅力值，这个魅力
值会随着彩蛋在空中降落的时间而降低，Sue 要想得到更多的分数，必须尽量在魅力值
高的时候收集这个彩蛋，而如果一个彩蛋掉入海中，它的魅力值将会变成一个负数，但
这并不影响Sue 的兴趣，因为每一个彩蛋都是不同的，Sue 希望收集到所有的彩蛋。
然而Sandy 就没有Sue 那么浪漫了，Sandy 希望得到尽可能多的分数，为了解决这
个问题，他先将这个游戏抽象成了如下模型：
以Sue 的初始位置所在水平面作为x 轴。
一开始空中有N 个彩蛋，对于第i 个彩蛋，他的初始位置用整数坐标（xi, yi）表
示，游戏开始后，它匀速沿y 轴负方向下落,速度为vi 单位距离/单位时间。Sue 的初始
位置为(x0, 0)，Sue 可以沿x 轴的正方向或负方向移动，Sue 的移动速度是1 单位距离
/单位时间，使用秘密武器得到一个彩蛋是瞬间的，得分为当前彩蛋的y 坐标的千分之
一。
现在，Sue 和Sandy 请你来帮忙，为了满足Sue 和Sandy 各自的目标，你决定在收
集到所有彩蛋的基础上，得到的分数最高。
【输入文件】
第一行为两个整数N, x0 用一个空格分隔，表示彩蛋个数与Sue 的初始位置。
第二行为N 个整数xi，每两个数用一个空格分隔，第i 个数表示第i 个彩蛋的初始
横坐标。
第三行为N 个整数yi，每两个数用一个空格分隔，第i 个数表示第i 个彩蛋的初始
纵坐标。
第四行为N 个整数vi，每两个数用一个空格分隔，第i 个数表示第i 个彩蛋匀速沿
y 轴负方向下落的的速度。
【输出文件】
一个实数，保留三位小数，为收集所有彩蛋的基础上，可以得到最高的分数。
【样例】
输入样例(ball.in 的内容)：
3 0
-4 -2 2
22 30 26
1 9 8
输出样例(ball.out 的内容)：
0.000
【数据范围】
N<=20，对于30%的数据。
N<=1000，对于100%的数据。
-10^4 <= xi,yi,vi <= 10^4，对于100%的数据。
动态规划
首先可以明确的是可以将x0左边和右边的彩蛋分组
按距离x0距离的顺序排序，存入两个队列中
y之和为最多达到的分数
用f[0][i][j]表示当前在队列1的i位置，队列2已该走j位置的分数减小最小值
用f[1][i][j]表示当前在队列2的j位置，队列1已该走i位置的分数减小最小值
转移方程为
f[0,i,j]=min(f[0,i-1,j]+(w1[i]+w2[j])*(s1[i-1].x-s1[i].x),f[1,i,j-1]+(w1[i]+w2[j])*(s2[j-1].x-s1[i].x))
f[1,i,j]=min(f[0,i-1,j]+(w1[i]+w2[j])*(s2[j].x-s1[i-1].x),f[1,i,j-1]+(w1[i]+w2[j])*(s2[j].x-s2[j-1].x))
当前在y坐标之和减去min(<当前在队列1队尾，队列2已走完的分数减小最小值>,<当前在队列2队尾，队列1已走完的分数减小最小值>)
测试数据
http://mail.qq.com/cgi-bin/ftnExs_download?k=716635352cf2cbcd6241402a1865011d065605050755041d1800020354500002554b0c0652541906555f0c180f5057011a560707045306510257000c00653c3255075959191755403720&t=exs_ftn_download&code=7f557e42
program ball;
const
thu:int64=1000;
type
point=record
x,v:longint;
end;
var
n,x0,i,j,k,t1,t2,d1,d2:longint;
ans:int64;
s1,s2,bal:array [0..1001] of point;
f:array [0..1,0..1001,0..1001] of int64;
w1,w2:array [0..1001] of int64;
procedure swap (var a,b:point);
var
i:point;
begin
i:=a;
a:=b;
b:=i;
end;
procedure qsort (s,e:longint);
var
i,j,k:longint;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=bal[(s+e) div 2].x;
while i<=j do
begin
while bal[i].x<k do inc(i);
while bal[j].x>k do dec(j);
if i>j then break;
swap(bal[i],bal[j]);
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
begin
assign(input,'ball.in');
reset(input);
assign(output,'ball.out');
rewrite(output);
read(n,x0);
ans:=0;
for i:=1 to n do
read(bal[i].x);
for i:=1 to n do
begin
read(k);
ans:=ans+k;
end;
for i:=1 to n do
read(bal[i].v);
qsort(1,n);
t1:=0;
d1:=0;
for i:=n downto 1 do
if bal[i].x<x0 then
begin
if (t1>0)and(bal[i].x=s1[t1].x) then
s1[t1].v:=s1[t1].v+bal[i].v
else
begin
inc(t1);
s1[t1]:=bal[i];
end;
d1:=d1+bal[i].v;
end;
t2:=0;
d2:=0;
for i:=1 to n do
if bal[i].x>x0 then
begin
if (t2>0)and(bal[i].x=s2[t2].x) then
s2[t2].v:=s2[t2].v+bal[i].v
else
begin
inc(t2);
s2[t2]:=bal[i];
end;
d2:=d2+bal[i].v;
end;
fillchar(f,sizeof(f),63);
s1[0].x:=x0;
for i:=t1 downto 0 do
w1[i]:=w1[i+1]+s1[i].v;
for i:=t2 downto 1 do
w2[i]:=w2[i+1]+s2[i].v;
s1[t1+1].x:=s1[t1].x;
s2[t2+1].x:=s2[t2].x;
f[0,0,1]:=0;
for i:=0 to t1+1 do
for j:=1 to t2+1 do
begin
if (i=t1+1)and(j=t2+1) then continue;
if (i<>t1+1)and(i>0)and(f[0,i,j]>f[0,i-1,j]+(w1[i]+w2[j])*(s1[i-1].x-s1[i].x)) then
f[0,i,j]:=f[0,i-1,j]+(w1[i]+w2[j])*(s1[i-1].x-s1[i].x);
if (j<>t2+1)and(i>0)and(f[1,i,j]>f[0,i-1,j]+(w1[i]+w2[j])*(s2[j].x-s1[i-1].x)) then
f[1,i,j]:=f[0,i-1,j]+(w1[i]+w2[j])*(s2[j].x-s1[i-1].x);
if (i<>t1+1)and(j>1)and(f[0,i,j]>f[1,i,j-1]+(w1[i]+w2[j])*(s2[j-1].x-s1[i].x)) then
f[0,i,j]:=f[1,i,j-1]+(w1[i]+w2[j])*(s2[j-1].x-s1[i].x);
if (j<>t2+1)and(j>1)and(f[1,i,j]>f[1,i,j-1]+(w1[i]+w2[j])*(s2[j].x-s2[j-1].x)) then
f[1,i,j]:=f[1,i,j-1]+(w1[i]+w2[j])*(s2[j].x-s2[j-1].x);
end;
if ans-f[0,t1,t2+1]>ans-f[1,t1+1,t2] then ans:=ans-f[0,t1,t2+1]
else ans:=ans-f[1,t1+1,t2];
writeln(ans/1000:0:3);
close(input);
close(output);
end.