Pasted

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
vector<int> villages;
int median[301][301];
int p[301][31];
// Интересно, оно работает?..
int cost(int l, int r){
    int med = median[l][r];
    int sum = 0;
    while(l <= r){
        sum += abs( villages[l] - villages[med] );
        l++;
    }
    return sum;
}
 
int main() {
    int dp[301][31];
    cin >> n >> m;
 
    villages.resize(n + 2);
    for(int i = 0; i < n; i++)
        cin >> villages[i];
    // Ура, мы справились прочитать!!!! *надеюсь верно*
 
    //Мда... Кто бы сомневался...
 
    // Тут мы как-то всё считаем для динамики
 
    for(int i = 0; i <= n; i++){
        int cur = i;
        for (int j = i; j <= n; j++){
            while (cur - i < j - cur - 1) cur++;
            median[i][j] = cur;
        }
    }
 
    for (int i = 1; i <= n; i++){
        dp[i][1] = cost(0, i-1);
        p[i][1] = 0;
    }
    // Ура!! Я осознала динамику ^^
    // Или нет...
    for (int cur = 1; cur <= n; cur++)
        for(int k = 2; k <= m; k++) {
            dp[cur][k] = 1000000;
            for (int i = 0; i <= cur; i++) {
                if (dp[cur][k] > dp[i][k - 1] + cost(i, cur-1)) {
                    dp[cur][k] = dp[i][k - 1] + cost(i, cur-1);
                    p[cur][k] = i;
                }
            }
        }
 
    cout << dp[n][m];
    return 0;
}