Untitled

#include <vector>
#include <limits>

int getMinTotalDistance(vector<int> dist_centers) {
    int n = dist_centers.size();
    
    // dp[i][j] represents the minimum total distance when considering
    // the first i distribution centers and placing j warehouses
    vector<vector<int>> dp(n + 1, vector<int>(3, numeric_limits<int>::max()));
    
    // Base case: 0 distribution centers
    dp[0][0] = 0;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= 2; ++j) {
            for (int k = 0; k < i; ++k) {
                // Try placing j-th warehouse at dist_centers[k]
                int cost = 0;
                for (int m = 0; m < i; ++m) {
                    // Calculate distance to the nearest warehouse
                    if (j == 1 || abs(dist_centers[m] - dist_centers[k]) < abs(dist_centers[m] - dist_centers[i-1])) {
                        cost += abs(dist_centers[m] - dist_centers[k]);
                    } else {
                        cost += abs(dist_centers[m] - dist_centers[i-1]);
                    }
                }
                
                if (k == 0) {
                    dp[i][j] = min(dp[i][j], cost);
                } else {
                    dp[i][j] = min(dp[i][j], dp[k][j-1] + cost);
                }
            }
        }
    }
    
    return dp[n][2];
}