#O1097. 玩具装箱

玩具装箱

题目描述

有 nn 个玩具,第 ii 个长度 cic_i。要把它们按顺序装进若干箱子,箱子的长度不超过 LL。若第 j+1j+1 到第 ii 个玩具装进一个箱子,则这个箱子的费用为

(∑k=j+1ick+i−j−1−L)2\left(\sum_{k=j+1}^{i} c_k + i-j-1 - L\right)^2

求把所有玩具装箱的最小总费用。

输入格式

第一行两个整数 n,Ln,L。

第二行 nn 个整数 cic_i。

输出格式

一行一个整数,表示最小总费用。

样例 #1

样例输入 #1

2 0
1 2

样例输出 #1

5

数据规模与约定

数据范围 说明
1≤n≤1051 \le n \le 10^5 玩具个数
0≤L≤5000 \le L \le 500 箱子容量
1≤ci≤10001 \le c_i \le 1000 每个玩具的长度
  • O(n2)O(n^2) 会超时,需要斜率优化把转移降到 O(1)O(1);决策点随 ii 单调,可以用单调队列维护下凸壳。