思路与算法

先以距离前缀和求村庄坐标x。令w[l][r]为这一连续段由一所学校服务的最小距离，选中位村庄，使用w[l][r]=w[l+1][r-1]+x[r]-x[l]预处理。dp[g][i]表示前i村恰建g校，转移枚举最后一段起点j+1：dp[g-1][j]+w[j+1][i]。利用最优决策单调性，分治计算每一层，候选j限制为[g-1,i-1]。

正确性说明

一维最近学校的服务区可按学校位置分为连续段；每段距离和在中位点最小，故对连续非空段划分枚举既不遗漏最优，又总能构造合法学校。区间中位距离具有Monge性质：对a≤b≤c≤d，w[a][c]+w[b][d]≤w[a][d]+w[b][c]；可按各相邻坐标间隙的贡献验证，其系数是左右村数的较小者。给w加上仅依赖j的上一层代价仍保持Monge性，选最左最优决策时随i不减，因此分治限制不排除最优。初值dp[0][0]=0，其他不可达。

复杂度

设D为坐标与答案的十进制位数。含预处理、初始化，时间O(m²D+nm log m D)，空间O(m²D+mD)；每层决策枚举在各分治深度总计O(m)。

易错点

学校必须在村庄且各段非空；n=m时答案0。距离只声明正整数，没有给位数上限，标程内置十进制大整数，不额外假定32位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct cpp_int {
    string s;
    bool neg;
    cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
        if (neg)
            s.erase(s.begin());
    }
    void norm() {
        auto p = s.find_first_not_of('0');
        s = p == string::npos ? "0" : s.substr(p);
        if (s == "0")
            neg = false;
    }
    static int cmpabs(const cpp_int &a, const cpp_int &b) {
        if (a.s.size() != b.s.size())
            return a.s.size() < b.s.size() ? -1 : 1;
        return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
    }
    friend bool operator<(const cpp_int &a, const cpp_int &b) {
        if (a.neg != b.neg)
            return a.neg;
        int c = cmpabs(a, b);
        return a.neg ? c > 0 : c < 0;
    }
    friend bool operator==(const cpp_int &a, const cpp_int &b) {
        return a.neg == b.neg && a.s == b.s;
    }
    friend bool operator!=(const cpp_int &a, const cpp_int &b) {
        return !(a == b);
    }
    friend bool operator>(const cpp_int &a, const cpp_int &b) {
        return b < a;
    }
    friend bool operator<=(const cpp_int &a, const cpp_int &b) {
        return !(b < a);
    }
    friend bool operator>=(const cpp_int &a, const cpp_int &b) {
        return !(a < b);
    }
    cpp_int operator-() const {
        cpp_int r = *this;
        if (r.s != "0")
            r.neg = !r.neg;
        return r;
    }
    friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
        cpp_int r;
        r.s.clear();
        int carry = 0;
        if (a.neg == b.neg) {
            int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                r.s += char('0' + v % 10);
                carry = v / 10;
            }
            r.neg = a.neg;
        } else {
            const cpp_int *x = &a, *y = &b;
            if (cmpabs(a, b) < 0)
                swap(x, y);
            int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
            while (i >= 0) {
                int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                carry = v < 0;
                if (carry)
                    v += 10;
                r.s += char('0' + v);
            }
            r.neg = x->neg;
        }
        reverse(r.s.begin(), r.s.end());
        r.norm();
        return r;
    }
    friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
        return a + (-b);
    }
    friend cpp_int operator*(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long carry = 0;
        long long z = b;
        if (z < 0)
            z = -z;
        for (int i = (int)a.s.size() - 1; i >= 0; i--) {
            carry += (a.s[i] - '0') * z;
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        while (carry) {
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        reverse(r.s.begin(), r.s.end());
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    friend cpp_int operator/(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long rem = 0, z = b;
        if (z < 0)
            z = -z;
        for (char c : a.s) {
            rem = rem * 10 + c - '0';
            r.s += char('0' + rem / z);
            rem %= z;
        }
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    cpp_int &operator+=(const cpp_int &b) {
        *this = *this + b;
        return *this;
    }
    cpp_int &operator-=(const cpp_int &b) {
        *this = *this - b;
        return *this;
    }
    cpp_int &operator*=(int b) {
        *this = *this * b;
        return *this;
    }
    friend istream &operator>>(istream &in, cpp_int &a) {
        string v;
        if (in >> v) {
            a.neg = v[0] == '-';
            if (v[0] == '-' || v[0] == '+')
                v.erase(v.begin());
            a.s = v;
            a.norm();
        }
        return in;
    }
    friend ostream &operator<<(ostream &out, const cpp_int &a) {
        if (a.neg)
            out << '-';
        return out << a.s;
    }
};

int main() {
    int m, n;
    cin >> m >> n;
    vector<cpp_int> x(m + 1);
    for (int i = 2; i <= m; i++) {
        cpp_int d;
        cin >> d;
        x[i] = x[i - 1] + d;
    }
    vector<vector<cpp_int>> w(m + 2, vector<cpp_int>(m + 2));
    for (int len = 2; len <= m; len++)
        for (int l = 1; l + len - 1 <= m; l++) {
            int rr = l + len - 1;
            w[l][rr] = w[l + 1][rr - 1] + x[rr] - x[l];
        }
    vector<cpp_int> old(m + 1), now(m + 1);
    vector<int> valid(m + 1);
    valid[0] = 1;
    for (int g = 1; g <= n; g++) {
        function<void(int, int, int, int)> calc = [&](int L, int R, int optL, int optR) {
            if (L > R)
                return;
            int mid = (L + R) / 2, best = -1;
            cpp_int value;
            for (int j = optL; j <= min(optR, mid - 1); j++)
                if (valid[j]) {
                    cpp_int v = old[j] + w[j + 1][mid];
                    if (best < 0 || v < value) {
                        value = v;
                        best = j;
                    }
                }
            now[mid] = value;
            calc(L, mid - 1, optL, best);
            calc(mid + 1, R, best, optR);
        };
        calc(g, m, g - 1, m - 1);
        old.swap(now);
        for (int i = 0; i <= m; i++)
            valid[i] = i >= g;
    }
    cout << old[m] << "\n";
}