HDU 1227 - Fast Food
Problem : N points in a line. Set M points to be 'chosen'. And make the total distance from each point to its nearest point minimum.
Solution : Let f[i][j] to be first j points' total minimum distance when the i-th 'chosen' point is j. Then f[i][j]=min{f[i-1][j-k]+cost(j-k+1, j-1)}, cost(i, j) is the total distance when i-1 and j+1 is the chosen point and the rest between them is not. Cost(i, j-1) to Cost(i, j) need O(1) when using queue to optimize. Thus the time complexity is O(mn^2) (m*n status, n strategies, with careful strategy picking order, the calculation of result of strategy takes O(1)).