ZOJ Monthly, August 2012 - E : Education Manage System

問題概要

重み付き区間がN(<10^5)個与えられる。隣同士5以上離れるように区間を選んで重みの和を最大化する問題。

解法

隣同士5離れているとかは全ての区間で右端を5伸ばせば良い。後は座標圧縮して重み付き区間スケジューリングに落とす。
コード略。