三、Sue 的小球
(ball.pas/c/cpp，限時0.5 秒，內(nèi)存256M)
【題目描述】
Sue 和Sandy 最近迷上了一個電腦游戲，這個游戲的故事發(fā)在美麗神秘并且充滿刺
激的大海上，Sue 有一支輕便小巧的小船。然而，Sue 的目標并不是當一個海盜，而是
要收集空中漂浮的彩蛋，Sue 有一個秘密武器，只要她將小船劃到一個彩蛋的正下方，
然后使用秘密武器便可以在瞬間收集到這個彩蛋。然而，彩蛋有一個魅力值，這個魅力
值會隨著彩蛋在空中降落的時間而降低，Sue 要想得到更多的分數(shù)，必須盡量在魅力值
高的時候收集這個彩蛋，而如果一個彩蛋掉入海中，它的魅力值將會變成一個負數(shù)，但
這并不影響Sue 的興趣，因為每一個彩蛋都是不同的，Sue 希望收集到所有的彩蛋。
然而Sandy 就沒有Sue 那么浪漫了，Sandy 希望得到盡可能多的分數(shù)，為了解決這
個問題，他先將這個游戲抽象成了如下模型：

以Sue 的初始位置所在水平面作為x 軸。

一開始空中有N 個彩蛋，對于第i 個彩蛋，他的初始位置用整數(shù)坐標（xi, yi）表
示，游戲開始后，它勻速沿y 軸負方向下落,速度為vi 單位距離/單位時間。Sue 的初始
位置為(x0, 0)，Sue 可以沿x 軸的正方向或負方向移動，Sue 的移動速度是1 單位距離
/單位時間，使用秘密武器得到一個彩蛋是瞬間的，得分為當前彩蛋的y 坐標的千分之
一。
現(xiàn)在，Sue 和Sandy 請你來幫忙，為了滿足Sue 和Sandy 各自的目標，你決定在收
集到所有彩蛋的基礎(chǔ)上，得到的分數(shù)最高。
【輸入文件】
第一行為兩個整數(shù)N, x0 用一個空格分隔，表示彩蛋個數(shù)與Sue 的初始位置。
第二行為N 個整數(shù)xi，每兩個數(shù)用一個空格分隔，第i 個數(shù)表示第i 個彩蛋的初始
橫坐標。

第三行為N 個整數(shù)yi，每兩個數(shù)用一個空格分隔，第i 個數(shù)表示第i 個彩蛋的初始
縱坐標。
第四行為N 個整數(shù)vi，每兩個數(shù)用一個空格分隔，第i 個數(shù)表示第i 個彩蛋勻速沿
y 軸負方向下落的的速度。
【輸出文件】
一個實數(shù)，保留三位小數(shù)，為收集所有彩蛋的基礎(chǔ)上，可以得到最高的分數(shù)。
【樣例】
輸入樣例(ball.in 的內(nèi)容)：
3 0
-4 -2 2
22 30 26
1 9 8
輸出樣例(ball.out 的內(nèi)容)：
0.000
【數(shù)據(jù)范圍】
N<=20，對于30%的數(shù)據(jù)。
N<=1000，對于100%的數(shù)據(jù)。
-10^4 <= xi,yi,vi <= 10^4，對于100%的數(shù)據(jù)。

動態(tài)規(guī)劃

首先可以明確的是可以將x0左邊和右邊的彩蛋分組

按距離x0距離的順序排序，存入兩個隊列中

y之和為最多達到的分數(shù)

用f[0][i][j]表示當前在隊列1的i位置，隊列2已該走j位置的分數(shù)減小最小值

用f[1][i][j]表示當前在隊列2的j位置，隊列1已該走i位置的分數(shù)減小最小值

轉(zhuǎn)移方程為

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已走完的分數(shù)減小最小值>,<當前在隊列2隊尾，隊列1已走完的分數(shù)減小最小值>)

測試數(shù)據(jù)

http://mail.qq.com/cgi-bin/ftnExs_download?k=716635352cf2cbcd6241402a1865011d065605050755041d1800020354500002554b0c0652541906555f0c180f5057011a560707045306510257000c00653c3255075959191755403720&t=exs_ftn_download&code=7f557e42

program ball; constthu:int64=1000; typepoint=recordx,v:longint;end; varn,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); vari:point; begini:=a;a:=b;b:=i; end;procedure qsort (s,e:longint); vari,j,k:longint; beginif s>=e then exit;i:=s;j:=e;k:=bal[(s+e) div 2].x;while i<=j dobeginwhile 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;beginassign(input,'ball.in');reset(input);assign(output,'ball.out');rewrite(output);read(n,x0);ans:=0;for i:=1 to n doread(bal[i].x);for i:=1 to n dobeginread(k);ans:=ans+k;end;for i:=1 to n doread(bal[i].v);qsort(1,n);t1:=0;d1:=0;for i:=n downto 1 doif bal[i].x<x0 thenbeginif (t1>0)and(bal[i].x=s1[t1].x) thens1[t1].v:=s1[t1].v+bal[i].velsebegininc(t1);s1[t1]:=bal[i];end;d1:=d1+bal[i].v;end;t2:=0;d2:=0;for i:=1 to n doif bal[i].x>x0 thenbeginif (t2>0)and(bal[i].x=s2[t2].x) thens2[t2].v:=s2[t2].v+bal[i].velsebegininc(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 dow1[i]:=w1[i+1]+s1[i].v;for i:=t2 downto 1 dow2[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 dofor j:=1 to t2+1 dobeginif (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)) thenf[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)) thenf[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)) thenf[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)) thenf[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.

總結(jié)

以上是生活随笔為你收集整理的Sue 的小球 ball的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。