OneDimensionalClustering

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

int N, K;
vector<vector<double>> dp;
const double INF = 2e15;

int main() {
    // Reading the number of instances and K value
    cin >> N >> K;
    assert(N >= K);

    dp.assign(N + 1, vector<double>(K + 1, INF));
    vector<vector<pair<int, int>>> parent(N + 1, vector<pair<int, int>>(K + 1, { INF, INF }));

    // DP initialization
    dp[0][0] = 0;

    // Reading the 1D instances
    vector<double> instances(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> instances[i];
    }

    // Sorting the instances
    sort(instances.begin(), instances.end());

    for (int i = 1; i <= N; ++i) {
        for (int k = 1; k <= K; ++k) {
            double squareSum = 0, sum = 0;
            for (int j = i; j >= k; --j) {
                squareSum += instances[j] * instances[j];
                sum += instances[j];
                double mean = sum / (i - j + 1);
                double cost = squareSum - (i - j + 1) * mean * mean;
                if (dp[j - 1][k - 1] + cost < dp[i][k]) {
                    dp[i][k] = dp[j - 1][k - 1] + cost;
                    parent[i][k] = { j - 1, k - 1 };
                }
            }
        }
    }

    cout << "The minimum J value obtained: " << dp[N][K] << '\n';
    cout << "The clusters formed are: \n";
    int n = N, k = K;

    // Solution reconstruction
    vector<vector<double>> clusters;
    while (k > 0) {
        clusters.emplace_back();
        pair<int, int> par = parent[n][k];
        for (int i = par.first + 1; i <= n; ++i) {
            clusters.back().push_back(instances[i]);
        }
        n = par.first, k = par.second;
    }

    reverse(clusters.begin(), clusters.end());

    // Printing the answer
    int index = 0;
    for (auto cluster : clusters) {
        index++;
        cout << "Cluster " << index << ":\n";
        for (double x : cluster) {
            cout << x << ' ';
        }
        cout << '\n';
    }
}