一栋楼有\(n\)层楼，有一座电梯，现有\(m\)个人在1层（底层）要上楼，第\(i\)个人的目标楼层为\(dst[i]\)，\(dst[i]>1\)。为了节省时间，电梯一次往返中只能停\(l\)次（即停靠在\(l\)个楼层上），每个人可以任选一个挺靠楼层走出电梯，并步行（上楼或下楼）至目的地。一个人往下走1层耗费\(d\)能量，往上走1层耗费\(u\)能量。问该电梯应该停靠在哪些楼层上，使得所有人的耗费最小。
令\(f(i,j)\)表示电梯停\(i\)个楼层，且停靠的最高那个楼层为\(j\)层的最小耗费，由于\(j+1\)层以上的耗费已由\(j\)固定，因此这时\(j\)层以下的耗费也是最小。令\(c_i\)表示在第\(i\)层楼下电梯的人数，则有：
\[f(i,j)=\min_{i\le k<j}\{f(i-1,k)-s_k+b_{kj}\}+s_j\]其中\(j\ge i+1\)，这是因为第1层不算在将要停靠的\(l\)个楼层上；而\(s_x\)表示所有目标楼层高于或等于\(x\)层的人从\(x\)层下楼并向上走到各自目标楼层的总耗费，可以用\(O(n)\)时间进行预处理，\(O(1)\)进行查询。
\(b_{kj}(k<j)\)表示所有目标楼层在\(k\)到\(j\)层之间（包括\(k\)和\(j\)层）的旅客的最小耗费。由于电梯不停靠任何\(k\)和\(j\)层之间（不包括\(k\)和\(j\)层）的楼层，因此这些旅客只能从\(k\)或\(j\)层下电梯。目标楼层在\(x(k\le x\le j)\)楼的人从\(j\)层往下走要\(d(j-x)\)，从\(k\)层往上走要\(u(x-k)\)，当\(d(j-x)\le u(x-k)\)，即\(x\ge\frac{dj+uk}{u+d}\)时，聪明的人都知道要从\(j\)层下电梯而不是\(k\)层。
令\(mid=\left\lceil \frac{dj+uk}{u+d}\right\rceil\)，令\(H_i\)表示目标为\(i\)楼以下（包括\(i\)楼）的人从1楼步行至各自目标的总耗费，\(T_i\)表示目标为\(i\)楼以上（包括\(i\)楼）的人从\(n\)楼下电梯并步行至各自目标的耗费，\(total_{i,j}\)表示目标楼层为\(i\)到\(j\)层的人数：\(total_{i,j}=sum_j-sum_{i-1}\)。则目标楼层为\(mid\)到\(j\)的人从\(j\)楼下电梯并步行至各自目标的总耗费为：
\[T_{mid}-T_{j+1}-total_{mid,j}(n-j)d\]而目标楼层为\(k\)到\(mid-1\)楼的人从\(k\)楼下电梯并步行至各自楼层的总耗费为：
\[H_{mid-1}-H_{k-1}-total_{k,mid-1}(k-1)u\]于是有：
\[\begin{eqnarray*} b_{kj} &=& T_{mid}-T_{j+1}-(sum_j-sum_{mid-1})(n-j)d \\ & & +H_{mid-1}-H_{k-1}-(sum_{mid-1}-sum_{k-1})(k-1)u \end{eqnarray*}\]这样\(b_{kj}\)可在\(O(1)\)时间内算出，因此状态转移方程的转移复杂度为\(O(n)\)，求解整个问题的复杂度为\(O(m+n^2l)\)。当n很大而m较小时，要离散化，目测要加个\(O(\log(n))\)的因子用来查找\(sum\)数组，而应该有均摊的方法去掉这个因子的。
当\(u=d=1\)时，该问题就是经典的1维K-means聚类问题（当然要对实数情况稍作更改）。自我臭美一下：可惜我没早点发现这个联系，不然这篇paper的作者估计就是我了：Optimal k-means Clustering in One Dimension by Dynamic Programming :)