回复 48楼 dongshimou
DP、背包，都沾点边。我还是具体解释一下吧。先考虑唱N首歌所需的最少时间是多少。唱每首歌所需的时间是固定的，差别在于两首歌之间调整音调所需的时间。
由于调整音调所需的时间是两首歌音调差的绝对值，为了直观我们将每首歌的音调按值排列在一根数轴上，两首歌之间调整音调所需时间就可以表示成数轴上两点间的线段长。
那么总的最短调整时间就该是最低音调与最高音调的差值（数轴上最左与最右点间的线段长）。原因，总的调整时间是连接所有点形成的路径的长度，在这些路径中，直线段最短（其它存在折返的线段总比这条直通的线段长吧）。
在此基础上，如果要删除一首歌后剩余的N-1首歌所需时间最短是多少？
删除数轴上中间的点只能减少单唱这首歌所需的时间，而调整音调所需的总时间不会减少。
删除数轴上的端点除了减少唱这首歌所需的时间还能减少一段它与相邻的最近点的距离（调整时间）。（当端点处重合多个点时可以认为它们都是端点，而它们与相邻最近点的距离为0）。
所以考察删除每个点所能减少的时间，选择所能减少时间最大的点删除，就是剩余N-1首歌演唱所需的最短时间。
首先计算唱所有歌曲所需的最短时间，如果超出时间限制则按上述方案删除一首歌，重复这一过程直至满足时间限制。这就是我的算法决策方案。由于时间关系就不写证明过程了，有兴趣的可以自己证明一下。
重剑无锋，大巧不工
