 /**//*
题意:长度为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;
}
|