Chương trình tìm chi phí gộp mảng số nguyên thành một giá trị duy nhất trong C++

Giả sử chúng ta được cung cấp một mảng arr chứa n số nguyên dương. Chúng ta cũng được cho một số nguyên j. Nhiệm vụ là gộp j số thành một số duy nhất bằng cách cộng chúng lại. Chi phí gộp bằng tổng của j số được chọn. Chúng ta phải tìm chi phí tối thiểu có thể cho phép gộp này.

Ví dụ, nếu arr = [2, 5, 6, 2, 3, 1, 3] và j = 4, thì kết quả sẽ là 31.

Chi phí gộp 2, 3, 1, 3 bằng 2 + 3 + 1 + 3 = 9.

Mảng sau phép gộp trở thành [2, 5, 6, 9]. Chi phí phép gộp thứ hai bằng 2 + 5 + 6 + 9 = 22. Tổng chi phí gộp là 22 + 9 = 31. Đây là chi phí gộp tối thiểu.

Giải thuật

• n := kích thước của arr
• Nếu (n - 1) mod (j - 1) khác 0, trả về -1
• Định nghĩa mảng temp(n + 1)
• Vòng lặp i từ n-1 đến 0: temp[i] := arr[i] + temp[i + 1]
• Định nghĩa mảng 2D dynArr cấp n x n
  • Vòng lặp k từ j đến n:
    • Vòng lặp le từ 0, rg = k - 1 cho đến rg < n:
      • dynArr[le][rg] := vô cực
      • Vòng lặp i từ le đến rg - 1, bước i += j - 1:
        • dynArr[le][rg] := min(dynArr[le][rg], dynArr[le][i] + dynArr[i + 1][rg])
      • Nếu (rg - le) mod (j - 1) == 0: dynArr[le][rg] += temp[le] - temp[rg + 1]
• Trả về dynArr[0][n - 1]

Ví dụ minh họa

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

int solve(vector<int>& arr, int j) { 
    int n = arr.size(); 
    if ((n - 1) % (j - 1) != 0) return -1; 
    vector<int> temp(n + 1); 
    for (int i = n - 1; i >= 0; i--) { 
        temp[i] = arr[i] + temp[i + 1]; 
    } 
    vector<vector<int>> dynArr(n, vector<int>(n)); 
    for (int k = j; k <= n; k++) { 
        for (int le = 0, rg = k - 1; rg < n; le++, rg++) { 
            dynArr[le][rg] = INT_MAX; 
            for (int i = le; i < rg; i += j - 1) { 
                dynArr[le][rg] = min(dynArr[le][rg], dynArr[le][i] + dynArr[i + 1][rg]); 
            } 
            if ((rg - le) % (j - 1) == 0) { 
                dynArr[le][rg] += temp[le] - temp[rg + 1]; 
            } 
        } 
    } 
    return dynArr[0][n - 1]; 
} 

int main() { 
    vector<int> arr = {2, 5, 6, 2, 3, 1, 3}; 
    cout << solve(arr, 4) << endl; 
    return 0; 
}

Đầu vào

{2, 5, 6, 2, 3, 1, 3}, 4

Đầu ra

31