Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
973 B
1
Indexable
Never
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

int minimumTotalCost(std::vector<int>& arr) {
    int n = arr.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(101, INT_MAX));
    
    // Initialize the DP table
    for (int j = 0; j <= 100; ++j) {
        dp[0][j] = 0;
    }
    
    // Fill the DP table
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= 100; ++j) {
            dp[i][j] = dp[i - 1][j] + std::abs(arr[i - 1] - j);
            if (i > 1) {
                dp[i][j] = std::min(dp[i][j], dp[i - 1][j]);
            }
        }
    }
    
    // Find the minimum cost
    int result = INT_MAX;
    for (int j = 0; j <= 100; ++j) {
        result = std::min(result, dp[n][j]);
    }
    
    return result;
}

int main() {
    std::vector<int> arr = {1, 4, 2, 1};
    std::cout << "Minimum Total Cost: " << minimumTotalCost(arr) << std::endl;
    return 0;
}
Leave a Comment