思路与算法

设总长为 $T$。目标展开为 $K^2\sum s_i^2-KT^2$，因此只需最小化各段长度平方和。复制数组一遍，用前缀和 $P$ 表示圆环连续段。

按原题规模分三种算法。$K=2$ 时，固定起点，另一个切口应使第一段和最接近 $T/2$；用单调双指针检查跨过一半的两侧切口。$K\notin\{2,3\}$ 时原题最大 $N=400,K=20$。枚举起点，做恰好 $K$ 段的线性分段DP。转移 $dp_t[i]=\min_{j<i}(dp_{t-1}[j]+(P_i-P_j)^2)$；把每个 $j$ 写为斜率 $-2P_j$、截距 $dp_{t-1}[j]+P_j^2$ 的直线，斜率递减、查询位置递增，用单调凸包每层线性完成。

$K=3$ 时可有 $N=300000$，不能枚举所有起点再做线性DP。三切口 $i<j<k<i+N$ 的平方和为 $Q(i,j,k)=(P_j-P_i)^2+(P_k-P_j)^2+(T+P_i-P_k)^2$。 最小的最优切口对 $(j_i,k_i)$ 随起点 $i$ 均不下降。对起点范围做分治：求中点的最优切口时，在已有 $j$ 范围内枚举；固定 $j$ 后，最佳 $k$ 是使 $P_k$ 最接近 $(P_j+P_i+T)/2$ 的合法前缀位置，可用双指针检查相邻两点。中点最优对同时作为左半的上界和右半的下界。每一层两个切口范围的总跨度为 $O(N)$，所以全部起点共用 $O(N\log N)$ 时间。

正确性说明

前缀和严格递增，因为所有舱室长度为正。固定一段的左右切口，另外两段的长度和固定，平方和在两者最接近时最小，故 $K=2$ 及 $K=3$ 中对另一个切口的相邻点检查都不漏最优。

证明三切口最优位置的单调性。将 $Q$ 展开，除各自单变量项外，三个交叉项均为 $-2P_iP_j,-2P_jP_k,-2P_iP_k$。由于 $P$ 递增，每项均满足子模交叉不等式，因此 $Q(u\wedge v)+Q(u\vee v)\le Q(u)+Q(v)$，其中最小/最大按三个坐标分别取。

取起点 $i<i'$ 的两个最优三元组。它们的逐坐标最小值仍是起点 $i$ 的合法三切口，逐坐标最大值仍是起点 $i'$ 的合法三切口：严格顺序及圆周窗口条件在这两个操作下都保持。由最优性与交叉不等式，两端所得三元组也最优。固定起点的最优切口集合对逐坐标最小封闭，因此存在唯一最小切口对；选字典序最小最优对即可取得该最小对。若较早起点的最小对有一个坐标超过较晚起点的最小对，逐坐标最小就会给出更小的同起点最优对，矛盾。故两个坐标均单调，分治传递的上下界始终包含真正最优解。

每次中点枚举全部允许的 $j$，并找到该 $j$ 的最佳 $k$；由单调性递归处理左右区间，不漏任何起点。其他 $K$ 的DP枚举最后一段左端点，恰好覆盖全部非空分段；凸包仅加速同一组直线的精确最小值。最后枚举所有起点，所有圆周划分都被覆盖，代回展开式即得答案。

复杂度

复制数组与前缀和初始化 $O(N)$。$K=2$ 为 $O(N)$ 时间；$K=3$ 每层分治切口总跨度 $O(N)$，共 $O(\log N)$ 层，时间 $O(N\log N)$。其他 $K$ 枚举 $N$ 个起点，每次 $K$ 层DP、每层 $O(N)$，总时间 $O(KN^2)$，对应原表 $N\le400,K\le20$。空间 $O(N)$，含输入、前缀和、滚动DP与凸包；递归栈 $O(\log N)$。平方和及最终答案用64位整数，凸包比较的乘积用128位。

易错点

圆环没有固定首段，不能只在原数组第一个位置做一次线性DP。必须恰分 $K$ 个非空段，不能允许空段。三切口优化依赖两个最优坐标同时单调，不能只凭“看起来均匀”贪心。代价相同时取字典序最小切口对，使单调性定义一致。$K=3$ 的大规模上界与其他 $K$ 的小规模分支必须按原表区别处理，不能把 $O(KN^2)$ 用到30万舱室。输出的是方差乘 $K^2$，不是只乘 $K$。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
const ll INF = 4000000000000000000LL;
struct Line {
    ll m, b;
    ll at(ll x) const {
        return m * x + b;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, K;
    if (!(cin >> n >> K))
        return 0;
    vector<ll> a(2 * n), s(2 * n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 0; i < 2 * n; ++i)
        s[i + 1] = s[i] + a[i];
    ll T = s[n], best = INF;
    if (K == 2) {
        int j = 1;
        for (int i = 0; i < n; ++i) {
            j = max(j, i + 1);
            while (j < i + n - 1 && 2 * (s[j] - s[i]) < T)
                ++j;
            for (int t = max(i + 1, j - 1); t <= j; ++t) {
                ll z = s[t] - s[i];
                best = min(best, z * z + (T - z) * (T - z));
            }
        }
    } else if (K == 3) {
        function<void(int, int, int, int, int, int)> solve = [&](int L, int R, int jl, int jr,
                                                                 int kl, int kr) {
            if (L > R)
                return;
            int i = (L + R) / 2, kmax = min(kr, i + n - 1), k = max(kl, i + 2), bj = -1, bk = -1;
            ll value = INF;
            for (int j = max(jl, i + 1); j <= min(jr, kmax - 1); ++j) {
                k = max(k, j + 1);
                ll target = s[j] + s[i] + T;
                while (k < kmax && 2 * s[k] < target)
                    ++k;
                for (int q = max(max(kl, j + 1), k - 1); q <= k && q <= kmax; ++q) {
                    ll x = s[j] - s[i], y = s[q] - s[j], z = T + s[i] - s[q],
                       v = x * x + y * y + z * z;
                    if (v < value || (v == value && make_pair(j, q) < make_pair(bj, bk))) {
                        value = v;
                        bj = j;
                        bk = q;
                    }
                }
            }
            best = min(best, value);
            solve(L, i - 1, jl, bj, kl, bk);
            solve(i + 1, R, bj, jr, bk, kr);
        };
        solve(0, n - 1, 1, 2 * n - 2, 2, 2 * n - 1);
    } else {
        for (int start = 0; start < n; ++start) {
            vector<ll> dp(n + 1, INF), ndp(n + 1);
            dp[0] = 0;
            for (int k = 1; k <= K; ++k) {
                fill(ndp.begin(), ndp.end(), INF);
                deque<Line> h;
                for (int i = k; i <= n; ++i) {
                    int j = i - 1;
                    if (dp[j] < INF) {
                        ll z = s[start + j] - s[start];
                        Line c{-2 * z, dp[j] + z * z};
                        while (h.size() > 1) {
                            Line b = h.back(), a = h[h.size() - 2];
                            if ((i128)(b.b - a.b) * (b.m - c.m) >= (i128)(c.b - b.b) * (a.m - b.m))
                                h.pop_back();
                            else
                                break;
                        }
                        h.push_back(c);
                    }
                    ll x = s[start + i] - s[start];
                    while (h.size() > 1 && h[0].at(x) >= h[1].at(x))
                        h.pop_front();
                    ndp[i] = x * x + h.front().at(x);
                }
                dp.swap(ndp);
            }
            best = min(best, dp[n]);
        }
    }
    cout << 1LL * K * K * best - 1LL * K * T * T << '\n';
}