首先考虑一个朴素dp。 我们将节目按照时刻排序，令  表示时刻  时，在位置  的最小不满值。 显然可以得到状态转移方程：  其中  表示时刻  时，位置  对当前时刻所有节目的不满值之和，即：  可以把状态转移方程写成：  容易观察到，如果用一个数组  来记录当前时刻的  值，那么  在时刻  的更新方式可以写成下面的两步：  对  前缀取 ，即 。 对每个满足  的 ，更新 。  那么  在时刻  的更新方式可以写成下面的两步：  对  的所有位置和  取 ，即 。 对每个满足  的 ，更新 ，对 ，更新 ，对 ，更新 。  下面证明第一步的正确性。 由于  是关于  的下凸函数，如果假定...