ধরুন আমাদের একটি অ্যারে দেওয়া হয়েছে যাতে n ধনাত্মক পূর্ণসংখ্যা রয়েছে। এছাড়াও আমাদের একটি পূর্ণসংখ্যা 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
- একটি অ্যারে টেম্প (n + 1) সংজ্ঞায়িত করুন
- আরম্ভ করার জন্য i :=n - 1, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), −
- করুন
- temp[i] :=arr[i] + temp[i + 1]
- ক্রম n x n
- এর একটি 2D অ্যারে dynArr সংজ্ঞায়িত করুন
- আরম্ভ করার জন্য k :=j, যখন k <=n, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করুন −
- লে শুরু করার জন্য :=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
