算法-算法问题，类似0-1背包

Question

现在有一个算法题：设公交车总共有N个站点，车上总共有m名乘客，每个乘客都在不同的车站下车，乘客下车的站分别为:n1,n2...nm ，公交车最多可以停车k次(k<m),请设计出该公交车的停车方案，使得顾客行走到目的地的距离最短。
(站点从0开始计数)
例如：
输入
N{0,10,12,14,20} //共五站，每个元素是相应站点距离起点的距离
M{1,2,3} //3个乘客，在第1，2，3站下车
k=1 //最多停1次
//
输出
方案:2 // 在第二站下车
行走距离:4

---

现在的思路是求N 和 K 的组合，然后求每一个组合的最小距离，最后返回最终结果，感觉效率不高，希望大家给点建议，有代码更好，谢谢!

Answer 1

这个问题可以用动态规划来解决.

首先, 没有人下车的站是肯定不会停的.

假设有m个人要下车, 但是只能停一次, 停车位置为m个人下车位置的中位数时, m个人走的距离之和最小(想一想为什么), 而没有人下车的站是不影响这些人的中位数的, 所以没人下车的站一定不会停.

由此可以容易预处理出dist[a][b], 表示在第a个与第b个要下车的人的位置之间停一次, 所有第a个到第b个人需要走的距离之和.

最后, 将M个人要下车的位置排序, 标号为1至M. 状态为dp[i][j],表示前i个人里停j次车能实现的最小距离和.状态转移方程为:
dp[i][j] = min{dp[k][j-1] + dist[k+1][i] | 0 < k < i}
问题答案为dp[M]K.

算法复杂度为O(M^2 * K).