【原创】编程之美---小飞的电梯调度问题 （停k层的解法） - Gavin的日志 - 网易博客

问题.有一栋楼，一共有N层，要去每一层的人分别是A[1],A[2]....A[N]，如果电梯可以停K次，问停在哪K层让所有人走的矩离最短？ [备注：这只是我的个人解法，欢迎和我讨论] 用一个数组opt[i][j]记录电梯前i次停在1到j层之间，所有人走的路的最短矩离。用cost[i][j]记录如果电梯从第i层到第j层只能停一次，电梯停在最佳位置让所有人走的矩离最短的最优解。那么cost[i][j]怎么求呢？（这里把这个解法省略，具体可参见编程之美“小飞的电梯调度”）。如果前i次停留在前j层，那么第i+1次停留在第j+1至j+k层(j+k<=n)，则状态转移方程为 opt[i+1][j+k]=min{opt[i][j]+cost[j+1][j+k];} (k+j<=n) Cost数组存放电梯从第i层到j层停一次的最小走动矩离，构造cost的代码如下：         } Opt[i][j] 表示从电梯在第1层到第j层停i次所有人的最小走动矩离，对于i=1（即电梯只停一次的情况）来说，opt[i][j] = cost[i][j],

Read full article from 【原创】编程之美---小飞的电梯调度问题 （停k层的解法） - Gavin的日志 - 网易博客