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