【第75题】继续刷区间八连刷（三）： 应难而上，[IOI2000] 邮局

10 5 
1 2 3 6 7 9 11 22 44 50

9

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>

using namespace std;
#define endl '\n';

namespace IO {
    const int MAXR = 10000000;
    char _READ_[MAXR], _PRINT_[MAXR];
    int _READ_POS_, _PRINT_POS_, _READ_LEN_;

    inline char readc() {
#ifndef ONLINE_JUDGE
        return getchar();
#endif
        if (!_READ_POS_) {
            if (feof(stdin)) return -1;
            _READ_LEN_ = fread(_READ_, 1, MAXR, stdin);
        }
        char c = _READ_[_READ_POS_++];
        if (_READ_POS_ == _READ_LEN_) _READ_POS_ = 0;
        return c;
    }

    template<typename T>
    inline int read(T &x) {
        x = 0;
        register int flag = 1, c;
        while (((c = readc()) < '0' || c > '9') && c != '-') {
            if (c < 0) {
                return -1;
            }
        }
        if (c == '-') {
            flag = -1;
        } else {
            x = c - '0';
        }
        while ((c = readc()) >= '0' && c <= '9') {
            x = x * 10 - '0' + c;
        }
        x *= flag;
        return 0;
    }
}//快读模版，老师倾情提供

inline int calc(int l, int r, vector<int> &a, vector<int> &prefix) {
    int mid = (l + r) / 2;
    return a[mid] * (mid - l + 1) - prefix[mid] + prefix[l - 1] +
           abs(a[mid] * (r - mid + 1) - prefix[r] + prefix[mid - 1]);
    //求区间和
}


void best_coder() {
    int v, p;
    IO::read(v);
    IO::read(p);
    vector<int> prefix(v + 2);
    vector<int> a(v + 2);
    vector<vector<int>> dp(v + 2, vector<int>(p + 2));
    vector<vector<int>> k(v + 2, vector<int>(p + 2));
  
    for (int i = 1; i <= v; ++i) {
        IO::read(a[i]);
        prefix[i] = a[i] + prefix[i - 1]; //先做个前缀和
    }
    for (int i = 1; i <= v; ++i) {
        dp[i][1] = calc(1, i, a, prefix);
    }
    for (int i = 1; i <= p; ++i) {
        k[v][i] = 1;
    }

    int cnt;
    for (int i = 2; i <= p; ++i) {
        k[v + 1][i] = v;
        dp[i][i] = 0;
        k[i][i] = i;
        for (int j = v; j > i; --j) {
            dp[j][i] = 0x7f7f7f7f;
            for (int s = k[j][i - 1]; s <= k[j + 1][i]; ++s) {
                cnt = calc(s + 1, j, a, prefix);
                if (dp[j][i] > dp[s][i - 1] + cnt) {
                    dp[j][i] = dp[s][i - 1] + cnt; //转移
                    k[j][i] = s;
                }
            }
        }
    }
    cout << dp[v][p];
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // freopen("xxx.in", "r", stdin);
    // freopen("xxx.out", "w", stdout);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // fclose(stdin);
    // fclose(stdout);

    return 0;
}