Tìm chi phí điều chỉnh tối thiểu của mảng trong C++

Khái niệm

Cho mảng số nguyên dương. Thay thế mỗi phần tử sao cho chênh lệch giữa hai phần tử liền kề ≤ target. Tối thiểu hóa chi phí điều chỉnh = Σ|A[i] - A_new[i]|. Tất cả phần tử < M = 100.

Ví dụ

Đầu vào: arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20

Đầu ra: Chi phí điều chỉnh tối thiểu = 35

Phương pháp Quy hoạch động

dp[i][j] = chi phí tối thiểu khi thay A[i] thành j. Mối quan hệ DP:

dp[i][j] = min{dp[i-1][k]} + |j - A[i]|, với mọi k sao cho |k - j| ≤ target.

Giới hạn: 0 ≤ i ≤ n, 0 ≤ j ≤ M (M=100). k từ max(j-target, 0) đến min(M, j+target). Kết quả: min{dp[n-1][j]} với 0 ≤ j ≤ M.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

#define M1 100

int minAdjustmentCost(int A1[], int n1, int target1) {
    int dp1[n1][M1 + 1];
    // Xử lý phần tử đầu riêng
    for (int j = 0; j <= M1; j++)
        dp1[0][j] = abs(j - A1[0]);
    // Các phần tử còn lại
    for (int i = 1; i < n1; i++) {
        for (int j = 0; j <= M1; j++) {
            dp1[i][j] = INT_MAX;
            for (int k = max(j - target1, 0); k <= min(M1, j + target1); k++)
                dp1[i][j] = min(dp1[i][j], dp1[i - 1][k] + abs(A1[i] - j));
        }
    }
    int res1 = INT_MAX;
    for (int j = 0; j <= M1; j++)
        res1 = min(res1, dp1[n1 - 1][j]);
    return res1;
}

int main() {
    int arr1[] = {56, 78, 53, 62, 40, 7, 26, 61, 50, 48};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int target1 = 20;
    cout << "Chi phí điều chỉnh tối thiểu là " << minAdjustmentCost(arr1, n1, target1) << endl;
    return 0;
}

Đầu ra

Chi phí điều chỉnh tối thiểu là 35