# Untitled

unknown
c_cpp
25 days ago
1.6 kB
3
Indexable
Never
```#include <vector>
#include <algorithm>
#include <iostream>
#include <climits>

using namespace std;

int getMinTotalDistance(vector<int> dist_centers) {
int n = dist_centers.size();

// Sort the distribution centers
sort(dist_centers.begin(), dist_centers.end());

// Calculate prefix sums of positions
vector<int> prefix_sum(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix_sum[i + 1] = prefix_sum[i] + dist_centers[i];
}

// Helper function to calculate the cost of placing one warehouse for a given range
auto get_cost = [&](int start, int end) {
int mid = (start + end) / 2;
int median = dist_centers[mid];
int cost = 0;
for (int i = start; i <= end; ++i) {
cost += abs(dist_centers[i] - median);
}
return cost;
};

// dp[i][k]: minimum cost for placing k warehouses up to the i-th distribution center
vector<vector<int>> dp(n + 1, vector<int>(3, INT_MAX));
dp[0][0] = 0;

// Fill the dp table
for (int k = 1; k <= 2; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
dp[i][k] = min(dp[i][k], dp[j][k - 1] + get_cost(j, i - 1));
}
}
}

// Return the result: minimum cost for placing 2 warehouses for all n centers
return dp[n][2];
}

// Example usage
int main() {
vector<int> dist_centers = {1, 2, 3};
cout << getMinTotalDistance(dist_centers) << endl;  // Output: 1

dist_centers = {1, 6};
cout << getMinTotalDistance(dist_centers) << endl;  // Output: 0

```