解题思路

我们想找到将数组分割成段的最小成本，使得段长度的平方和最小。
我们可以使用单调队列来跟踪最优的段长度。
我们遍历数组，对于每个元素，找到之前队列中的最优段长度。
我们更新动态规划表 d，其中包含将数组分割成段的最小成本，直到当前元素。
我们使用公式 d[i] = d[j] + (s[i] - s[j])^2 计算最小成本，其中 j 是队列中的前一个元素。
公式：

公式 d[i] = d[j] + (s[i] - s[j])^2 可以从以下推导：

让 d[i] 是将数组分割成段的最小成本，直到 i-th 元素。
让 j 是队列中的前一个元素，使得 s[j] + cnt[j] <= s[i]。
让 cnt[i] 是以 i-th 元素结束的段的长度。

那么，将数组分割成段的成本是最小的：

将数组分割成段的成本，直到 j-th 元素 (d[j])
添加一个新的段从 j+1 到 i 的成本 ((s[i] - s[j])^2）
因此，d[i] = d[j] + (s[i] - s[j])^2。

伪代码

d[0] = 0, cnt[0] = 0

for i = 1 to n:
    while qr > ql and s[q[ql+1]] + cnt[q[ql+1]] <= s[i]:
        ++ql
    if qr >= ql and s[q[ql]] + cnt[q[ql]] <= s[i]:
        d[i] = d[q[ql]] + (s[i] - s[q[ql]])^2
        cnt[i] = s[i] - s[q[ql]]
    while qr >= ql and s[i] + cnt[i] <= s[q[qr]] + cnt[q[qr]]:
        --qr
    q[++qr] = i

print d[n]