Untitled
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