C++でストーンをマージするための最小コスト

N個の石の山が一列に並んでいると仮定します。ここで、i番目の山には石[i]個の石があります。移動は、K個の連続する杭を1つの杭にマージすることで構成されます。この移動のコストは、これらのK個の杭の石の総数に等しくなります。すべての石の山を1つの山に統合するための最小コストを見つける必要があります。そのような解決策がない場合は、-1を返します。

したがって、入力が[3,2,4,1]のようで、K =2の場合、出力は20になります。これは、[3、2、4、1]から開始するためです。次に、[3、2]を5のコストでマージすると、[5、4、1]が残ります。その後、5のコストで[4、1]をマージし、[5、5]が残ります。次に、[5、5]を10のコストでマージすると、[10]が残ります。つまり、総コストは20で、これが最小のコストです。

これを解決するには、次の手順に従います-

• n：=石のサイズ

• （n-1）mod（k-1）が0に等しくない場合、-

  • -1を返す

• サイズn+1の配列プレフィックスを定義します

• 初期化i：=1の場合、i <=nの場合、更新（iを1増やします）、実行-

  • prefix [i]：=prefix [i-1] + stones [i-1]

• サイズnxn

  の2D配列dpを1つ定義します。

• 長さの初期化：=kの場合、長さ<=nの場合、更新（長さを1増やします）、実行-

  • 初期化i：=0、j：=長さ-1の場合、j

  • dp [i、j]：=inf

  • mid：=iを初期化する場合、mid

    • dp [i、j]：=最小のdp [i、j]およびdp [i、mid] + dp [mid + 1、j]

  • （j --i）mod（k --1）が0と同じ場合、-

    • dp [i、j]：=dp [i、j]+プレフィックス[j+1]-プレフィックス[i]

• dp [0、n-1]

  を返します

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int mergeStones(vector<int>& stones, int k){
      int n = stones.size();
      if ((n - 1) % (k - 1) != 0)
      return -1;
      vector<int> prefix(n + 1);
      for (int i = 1; i <= n; i++) {
         prefix[i] = prefix[i - 1] + stones[i - 1];
      }  
      vector<vector<int>> dp(n, vector<int>(n));
      for (int length = k; length <= n; length++) {
         for (int i = 0, j = length - 1; j < n; i++, j++) {
            dp[i][j] = INT_MAX;
            for (int mid = i; mid < j; mid += k - 1) {
               dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid +
               1][j]);
            }
            if ((j - i) % (k - 1) == 0) {
               dp[i][j] += prefix[j + 1] - prefix[i];
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,4,1};
   cout << (ob.mergeStones(v, 2));
}

入力

{3,2,4,1}, 2

出力

20