C++에서 정수 배열을 단일 값으로 병합하는 비용을 찾는 프로그램

<시간/>

n개의 양의 정수를 포함하는 배열 arr이 주어졌다고 가정합니다. 정수 j도 주어진다. 우리가 수행해야 하는 작업은 j개의 숫자를 추가하여 단일 숫자로 병합하는 것입니다. 병합 비용은 우리가 선택한 j개의 숫자를 더한 것과 같습니다. 이 병합 작업에 대해 가능한 최소 비용을 찾아야 합니다.

따라서 입력이 arr =[2, 5, 6, 2, 3, 1, 3], j =4와 같으면 출력은 31이 됩니다.

2, 3, 1, 3을 병합하는 데 드는 비용은 2 + 3 + 1 + 3 =9와 같습니다.

병합 작업 후의 배열은 [2, 5, 6, 9]가 됩니다. 두 번째 병합 작업의 비용은 2 + 5 + 6 + 9 =22와 같습니다. 따라서 병합 작업의 총 비용은 22 + 9 =31이 됩니다. 이것이 최소 병합 비용입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=arr의 크기
(n - 1) mod(j - 1)가 0과 같지 않으면 -
- 반환 -1
배열 temp(n + 1) 정의
초기화 i의 경우:=n - 1, i>=0일 때 업데이트(i를 1만큼 감소), 수행 -
- temp[i] :=arr[i] + temp[i + 1]
n x n
- 초기화 k :=j의 경우 k <=n일 때 업데이트(k를 1만큼 증가), 다음을 수행합니다. -
- 초기화 le :=0, rg :=k - 1, rg
- dynArr[le, rg] :=inf
- 초기화 i :=le의 경우, i 을 수행합니다.
- dynArr[le, rg] :=(dynArr[le, rg] 및 dynArr[le, i] + dynArr[i + 1, rg])의 최소값
(rg - le) mod(j - 1)가 0과 같으면 -
- dynArr[le, rg] :=dynArr[le, rg] + 임시[le] - 임시[rg + 1]

dynArr[0, n - 1]을 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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;
}

입력

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