Chương trình tìm ra chi phí để hợp nhất một 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 tôi cũng được cung cấp một số nguyên j. Nhiệm vụ mà chúng ta phải thực hiện là hợp nhất các số j thành một số duy nhất bằng cách cộng chúng. Chi phí hợp nhất bằng với việc cộng các số j mà chúng ta đã chọn. Chúng tôi phải tìm ra chi phí tối thiểu có thể có cho hoạt động hợp nhất này.

Vì vậy, nếu đầu vào là arr =[2, 5, 6, 2, 3, 1, 3], j =4, thì đầu ra sẽ là 31.

Chi phí để hợp nhất 2, 3, 1, 3 bằng 2 + 3 + 1 + 3 =9.

Mảng sau khi thực hiện hợp nhất trở thành [2, 5, 6, 9]. Chi phí của hoạt động hợp nhất thứ hai bằng 2 + 5 + 6 + 9 =22. Vì vậy, tổng chi phí của hoạt động hợp nhất trở thành 22 + 9 =31. Đây là chi phí hợp nhất tối thiểu.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của arr
• nếu (n - 1) mod (j - 1) không bằng 0, thì -
  • trả về -1
• Xác định tạm thời mảng (n + 1)
• để khởi tạo i:=n - 1, khi i> =0, cập nhật (giảm i đi 1), thực hiện -
  • temp [i]:=arr [i] + temp [i + 1]
• Xác định một mảng 2D dynArr có thứ tự n x n
  • để khởi tạo k:=j, khi k <=n, cập nhật (tăng k lên 1), thực hiện -
  • để khởi tạo le:=0, rg:=k - 1, khi rg
  • dynArr [le, rg]:=inf
  • để khởi tạo i:=le, khi i
  • dynArr [le, rg]:=tối thiểu là (dynArr [le, rg] và dynArr [le, i] + dynArr [i + 1, rg])
• if (rg - le) mod (j - 1) giống 0, thì -
  • dynArr [le, rg]:=dynArr [le, rg] + temp [le] - temp [rg + 1]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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