C++で整数の配列を単一の値にマージするコストを見つけるためのプログラム

n個の正の整数を含む配列arrが与えられたと仮定します。整数jも与えられます。実行する必要のあるタスクは、j個の数値を加算して1つの数値にマージすることです。マージのコストは、選択した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番目のマージ操作のコストは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]
• 次数nxn
  の2D配列dynArrを1つ定義します。
  • 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] + temp [le] --temp [rg + 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

出力

31