 /**//*
題意:長度為L寬為W的馬路的一旁有n棵樹(給出位置),現需把這個n棵樹移動到馬路兩旁
使得同一排的樹的間距相等,位置0和L處必須放樹,求最小移動距離

如果只有一排的馬路,只需要按順序移動到相應的洞即可。但現在有2排
某棵樹x最后被安置的位置可以有很多個,左右兩旁都行
但是可以按樹的坐標順序一棵一棵去種在第一個空的位置(左右都行)是最優的
這個空的位置需要枚舉出來,可左可右

用dp[left,right]表示用前left+right棵樹種在左邊前left個,右邊前right個的最小移動距離,則
dp[left,right] = min(dp[left-1,right]+dist1,dp[left,right-1]+dist2)

我一開始把焦點放在樹上,做不出
應該放在馬路上
而一個顯然的道理是按照樹的順序種,然后需要枚舉種的這個最后的位置!
*/
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

double dp[1010][1010];
double tree[2010];

inline double dist(double x1,double y1,double x2,double y2)
  {
x1-=x2;
y1-=y2;
return sqrt(x1*x1+y1*y1);
}
int main()
  {
//freopen("in","r",stdin);
int n,L,W;
while(~scanf("%d",&n))
 {
scanf("%d%d",&L,&W);
double avg = L/(n/2-1.0);
for(int i=0;i<n;i++)
scanf("%lf",&tree[i]);
sort(tree,tree+n);
//dp[left,right] = min(dp[left-1,right]+dist1,dp[left,right-1]+dist2)
dp[0][0]=0.0;
for(int left=0;left<=n/2;left++)
for(int right=0;right<=n/2;right++)
 {
if(left==0&&right==0)continue;
double &ans=dp[left][right];
ans = 1e30;
int id=left+right-1;//the one to plant
if(left)ans = min( ans , dp[left-1][right] + dist(0.0,tree[id],0.0,avg*(left-1)));
if(right)ans = min( ans , dp[left][right-1] + dist(0.0,tree[id],W+0.0,avg*(right-1)));
}
printf("%.6f\n",dp[n/2][n/2]);
}
return 0;
}
|