最大值的块数是有限制的，由于它是 10^3 约束，因此它具有 dp[10^3][10^3] 的感觉。 从这里开始， dp[i][m] ：= 当第 i 个苹果装进 m 盒子时，美人的最大和状态的数量 约为 10^6，因此您需要进行过渡。 如果你正常执行 transition destination，则有 O（N） street，但让我们使用 greed 方法减少这里的 transition。

首先，重要的特性是“装很多苹果不降低美感”。 换句话说，如果最大值和最小值相同，则尽可能少地包装苹果并让苹果 稍后填充的策略是有效的。 因此，过渡目的地是“只需要看到最大值和最小值变化的边界”。

找到该边界的最快方法是使用 NXT 数组。 nxt[i][a] ：= 密度为 a 的第 i 个苹果之后最近的苹果是什么？ 这可以用累积最小值快速计算。 这样，如果我们认为苹果被装在盒子里，其中 i+1st 苹果是最左边的选择， 那么 nxt[i][1]， nxt[i][2]， ... ， nxt[i][6] 是最右边的候选者。 如果对此进行排序，则当右边缘按顺序拉伸时，可以看到最大值和最小值的变化。 这将进行过渡。

答案是每次将右边缘延伸到最边缘时取 beauty 之和的最大值。