萌新初学斜率优化~
首先设 \(sum_i = \sum\limits_{j = 1}^i c_j\)。
有转移方程 \(f_i = \min\limits_{0 \le j < i}(f_j + (i - j - 1 + sum_i - sum_j - L)^2)\)。
设 \(A_i = sum_i + i,B_i = A_i + L + 1\)，则原式变为 \(f_i = \min\limits_{0 \le j < i}(f_j + (A_i - B_j)^2)\)。
考虑 \(0 \le k < j < i\)，假设此时选 \(j\) 比选 \(k\) 更优，即 \(f_j + (A_i - B_j)^2 \le f_k + (A_i - B_k)^2\)。
来推一波不等式： \[\begin{align*}
f_j + (A_i - B_j)^2 & \le f_k + (A_i - B_k)^2 \\
f_j + A_i^2 - 2A_iB_j + B_j^2 & \le f_k + A_i^2 - 2A_iB_k + B_k^2 \\
f_j - 2A_iB_j + B_j^2 & \le f_k - 2A_iB_k + B_k^2 \\
(f_j + B_j^2) - (f_k + B_k^2) & \le 2A_i(B_j - B_k)
\end{align*}\]
注意到 \(c_i\) 都是正整数，于是有 \(B_j > B_k\)。 \[\begin{align*} (f_j + B_j^2) - (f_k + B_k^2) & \le 2A_i(B_j - B_k) \\ \dfrac{(f_j + B_j^2) - (f_k + B_k^2)}{B_j - B_k} & \le 2A_i \end{align*}\]
这玩意像什么？斜率！
我们在单调队列中维护一个下凸包（即相邻两点线段斜率单调上升的一个点集）。
然后每次从队头开始，在满足条件之前一直把队头扔掉（即我们刚才推出来的结论）。
这个时候的队头就是最优决策了（易证，其实是我懒）。
然后把当前的点入队，注意维护单调性。
这个方法没有几乎涉及到任何几何知识（斜率那些不算，就算你不知道也能看懂），纯粹是在代数层面推出的斜率优化，比较适宜新人理解。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using namespace std;
const int N = 5e4;
int n,l,c[N + 5];
int q[N + 5],head,tail;
long long A[N + 5],B[N + 5],sum[N + 5],f[N + 5];
inline double slope(int x,int y)
{
return (double)(f[x] + B[x] * B[x] - f[y] - B[y] * B[y]) / (B[x] - B[y]);
}
int main()
{
scanf("%d%d",&n,&l);
B[0] = l + 1;
for(register int i = 1;i <= n;++i)
scanf("%d",c + i),B[i] = (A[i] = (sum[i] = sum[i - 1] + c[i]) + i) + l + 1;
q[head = tail = 1] = 0;
for(register int i = 1;i <= n;++i)
{
for(;head < tail && slope(q[head],q[head + 1]) <= 2 * A[i];++head);
f[i] = f[q[head]] + (A[i] - B[q[head]]) * (A[i] - B[q[head]]);
for(;head < tail && slope(q[tail - 1],q[tail]) >= slope(q[tail],i);--tail);
q[++tail] = i;
}
printf("%lld\n",f[n]);
}