0w1

Slope

POJ 1180 Batch Scheduling ( Slope Optimization DP )

1180 -- Batch Scheduling題意: 有 N 個工作,用 T[ i ], F[ i ] 描述第 i 個工作需要花費的時間,以及單位時間的價值。第 i + 1 個工作不能在第 i 個工作完成之前被完成。每次可以選擇 k 個,未完成的工作中編號最小的工作,花費其 T 的總和,令之 P,的時…

Monotonous slope optimization DP

This optimization is also called "Convex Hull Trick" because it is either maintaining an upper convex hull ( decreasing slopes ) or a lower convex hull. Also note that there are problems that do not necessarily have to be monotonous but st…