C++ এ স্টোন মার্জ করার ন্যূনতম খরচ

ধরুন আমাদের একটি সারিতে সাজানো পাথরের স্তূপ আছে। এখানে i-th স্তূপে পাথর [i] সংখ্যক পাথর রয়েছে। একটি পদক্ষেপে K পরপর পাইলগুলিকে একটি স্তূপে একত্রিত করা হয়, এখন এই পদক্ষেপের খরচ এই K সংখ্যক পাইলের মোট পাথর সংখ্যার সমান। সমস্ত পাথরের স্তূপকে এক স্তূপে একত্রিত করার জন্য আমাদের সর্বনিম্ন খরচ খুঁজে বের করতে হবে। যদি এমন কোন সমাধান না থাকে, তাহলে -1 রিটার্ন করুন।

সুতরাং, যদি ইনপুটটি [3,2,4,1] এবং K =2 এর মত হয়, তাহলে আউটপুট হবে 20, এর কারণ, আমরা [3, 2, 4, 1] দিয়ে শুরু করব। তারপর আমরা 5 খরচের জন্য [3, 2] মার্জ করি, এবং আমাদের [5, 4, 1] বাকি থাকে। এর পরে আমরা 5 খরচের জন্য [4, 1] মার্জ করি, এবং আমাদের [5, 5] বাকি থাকে। তারপর আমরা 10 খরচের জন্য [5, 5] মার্জ করি, এবং আমরা [10] এর সাথে বাকি থাকি। সুতরাং, মোট খরচ ছিল 20, এবং এটি সর্বনিম্ন।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=পাথরের আকার

• যদি (n - 1) mod (k - 1) 0 এর সমান না হয়, তাহলে −

  • রিটার্ন -1

• আকার n + 1

  এর একটি অ্যারে উপসর্গ সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

  • উপসর্গ[i] :=উপসর্গ[i - 1] + পাথর[i - 1]

• n x n

  আকারের একটি 2D অ্যারে dp সংজ্ঞায়িত করুন

• শুরুর দৈর্ঘ্যের জন্য :=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[মধ্য + 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