思路与算法

设Si是前缀权值和，dp[i]为前i词最小费用。转移dp[i]=Si²+M+min_j(dp[j]+Sj²−2SiSj)。每个j对应直线斜率−2Sj、截距dp[j]+Sj²；Si非递减，斜率非递增，用双端队列维护下凸包并按单调x查询。相同斜率只保留较小截距。

正确性说明

最优分段最后一段必是j+1..i，去掉它后前j项须取dp[j]，否则能替换成更优解。因此原DP枚举完全。平方展开仅作代数变形，不改变最小值。单调查询时，某条直线已被后一条在当前x超越，在更大的x也不会再次变优；插入时删除永无独占最优区间的中间直线。队列恰保留有效下包络，得到正确转移。

复杂度

前缀与dp初始化O(1)，每条直线各进出队列至多一次，总O(N)时间、O(N)空间；多组总O(ΣN+组数)。

易错点

Ci可为0，重复斜率必须比较截距，不能直接交点除法。比较交点用128位叉乘；dp和Si²用64位。N0输出0；M0、全零权与多组EOF都要处理。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using I = __int128_t;
struct Line {
    ll m, b;
    ll at(ll x) const {
        return m * x + b;
    }
};
bool bad(Line a, Line b, Line c) {
    return (I)(b.b - a.b) * (b.m - c.m) >= (I)(c.b - b.b) * (a.m - b.m);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll M;
    while (cin >> n >> M) {
        deque<Line> h;
        h.push_back({0, 0});
        ll sum = 0, dp = 0;
        for (int i = 0; i < n; i++) {
            ll x;
            cin >> x;
            sum += x;
            while (h.size() > 1 && h[0].at(sum) >= h[1].at(sum))
                h.pop_front();
            dp = sum * sum + M + h[0].at(sum);
            Line z{-2 * sum, dp + sum * sum};
            while (!h.empty() && h.back().m == z.m) {
                if (h.back().b <= z.b)
                    break;
                h.pop_back();
            }
            if (!h.empty() && h.back().m == z.m)
                continue;
            while (h.size() > 1 && bad(h[h.size() - 2], h.back(), z))
                h.pop_back();
            h.push_back(z);
        }
        cout << dp << '\n';
    }
}