Description

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各自的目標，你決定在收集到所有彩蛋的基礎上，得到的分數最高。

Input

第一行為兩個整數N, x0用一個空格分隔，表示彩蛋個數與Sue的初始位置。?
第二行為N個整數xi，每兩個數用一個空格分隔，第i個數表示第i個彩蛋的初始橫坐標。?
第三行為N個整數yi，每兩個數用一個空格分隔，第i個數表示第i個彩蛋的初始縱坐標。?
第四行為N個整數vi，每兩個數用一個空格分隔，第i個數表示第i個彩蛋勻速沿y軸負方向下落的的速度。

Output

一個實數，保留三位小數，為收集所有彩蛋的基礎上，可以得到最高的分數。

Sample Input

3 0 -4 -2 2 22 30 26 1 9 8

Sample Output

0.000

Hint

N<=20，對于30%的數據。?
N<=100，對于100%的數據。?
-10^4 <= xi,yi,vi <= 10^4，對于100%的數據。?

【分析】

顯然，Sue沒浪費一單位時間，所有他沒有接到的彩蛋都會損失一定的分數。
設
a[n]表示Sue起始點左邊的所有點距Sue的距離，按從小到大排序；
b[m]表示Sue起始點右邊的所有點距Sue的距離，按從小到大排序。
Sum_a[i]表示一單位時間a數組中前i個彩蛋損失的分數的前綴和；
Sum_b[i]表示一單位時間b數組中前i個彩蛋損失的分數的前綴和。

用動態規劃解決此題：
設狀態為f[i][j][k]表示Sue的起始點左邊收集了i個彩蛋，右邊收集了j個彩蛋，并且最終停留在位置k（k=0表示停在左邊i位置上，k=1表示停在右邊j位置上）時最小的損失。
狀態轉移方程為：
f[i][j][0] = min{
? ? ? ? ? ? ? ?f[i-1][j][0] + (a[i]-a[i-1])*(Sum_a[n]-Sum_a[i-1]+Sum_b[m]-Sum_b[j]),
　　　 f[i-1][j][1] + (a[i]+b[j])*(Sum_a[n]-Sum[i-1]+Sum_b[m]-Sum_b[j]
? ? ? ? ? ? ? ? }
f[i][j][1] = min{
? ? ? ? ? ? ? ?f[i][j-1][1] + (b[j]-b[j-1])*(Sum_a[n]-Sum_a[i]+Sum_b[m]-Sum_b[j-1],
? ? ? f[i][j-1][0] + (a[i]+b[j])*(Sum_a[n]-Sum_a[i]+Sum_b[m]-Sum_b[j-1])
? ? ? ? ? ? ? ? }
最后的結果即為初始分數減去min{f[n][m][0], f[n][m][1]}

【代碼】

/*ID:CiocioLANG:C++DATE:2013-11-30TASK:SDOI 2008 Sue */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <queue>using namespace std;#define MAXN 1005 #define INF 999999999struct node{int x,sum;friend bool operator<(const node &A,const node &B){return A.x<B.x;} }; node A[MAXN],B[MAXN]; int N,x0,f[MAXN][MAXN][2],x[MAXN],y[MAXN],v[MAXN]; int n,m,tot;void _init() {scanf("%d%d",&N,&x0);for(int i=1;i<=N;i++) scanf("%d",&x[i]);for(int i=1;i<=N;i++) scanf("%d",&y[i]),tot+=y[i];for(int i=1;i<=N;i++) scanf("%d",&v[i]);for(int i=1;i<=N;i++){if(x[i]<x0) //前面的放入結構體A{n++;A[n].x=x0-x[i];A[n].sum=v[i];} else if(x[i]>x0) //后面的放入B{m++;B[m].x=x[i]-x0;B[m].sum=v[i];}}sort(A+1,A+n+1);sort(B+1,B+m+1); //排序for(int i=1;i<=n;i++) //求出代價的前綴和A[i].sum+=A[i-1].sum;for(int i=1;i<=m;i++) B[i].sum+=B[i-1].sum; }void _solve() {for(int i=1;i<=n;i++) //邊界{f[i][0][0]=f[i-1][0][0]+(A[i].x-A[i-1].x)*(B[m].sum+A[n].sum-A[i-1].sum);f[i][0][1]=f[i][0][0]+A[i].x*(B[m].sum+A[n].sum-A[i].sum);}for(int i=1;i<=m;i++){f[0][i][1]=f[0][i-1][1]+(B[i].x-B[i-1].x)*(A[n].sum+B[m].sum-B[i-1].sum);f[0][i][0]=f[0][i][1]+B[i].x*(A[n].sum+B[m].sum-B[i].sum);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) //DP{int delta1=A[n].sum-A[i-1].sum+B[m].sum-B[j].sum;int delta2=A[n].sum-A[i].sum+B[m].sum-B[j-1].sum;f[i][j][0]=min(f[i-1][j][0]+(A[i].x-A[i-1].x)*delta1,f[i-1][j][1]+(A[i].x+B[j].x)*delta1);f[i][j][1]=min(f[i][j-1][0]+(A[i].x+B[j].x)*delta2,f[i][j-1][1]+(B[j].x-B[j-1].x)*delta2);}printf("%.3lf\n",(double)(tot-min(f[n][m][0],f[n][m][1]))/1000.0); }int main() {_init();_solve();return 0; }

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。