ধরা যাক আমাদের একটি অ্যারে arr দেওয়া আছে যাতে nটি ধনাত্মক পূর্ণসংখ্যা রয়েছে। আমাদের একটি পূর্ণসংখ্যা jও দেওয়া আছে। আমাদের কাজ হলো jটি সংখ্যা বেছে নিয়ে যোগ করে একটি একক সংখ্যা তৈরি করা। মার্জ করার খরচ হবে নির্বাচিত jটি সংখ্যার যোগফলের সমান। এই মার্জ অপারেশনটির ন্যূনতম সম্ভাব্য খরচ বের করতে হবে।
উদাহরণস্বরূপ, arr = [2, 5, 6, 2, 3, 1, 3], j = 4 হলে আউটপুট হবে ৩১।
প্রথমে 2, 3, 1, 3 মার্জ করা হয়, খরচ = ২+৩+১+৩ = ৯। অ্যারে হয়ে যায় [2, 5, 6, 9]। দ্বিতীয় মার্জের খরচ = ২+৫+৬+৯ = ২২। মোট খরচ = ২২+৯ = ৩১, যা ন্যূনতম।
সমাধানের ধাপসমূহ
- n := arr-এর আকার
- যদি (n - 1) mod (j - 1) ≠ 0 হয়, তবে -1 রিটার্ন করুন
- আকার n+1-এর একটি temp অ্যারে সংজ্ঞায়িত করুন
- i := n-1 থেকে ০ পর্যন্ত লুপ চালিয়ে temp[i] := arr[i] + temp[i + 1] হিসাব করুন
- n x n আকারের একটি ২D ডাইনামিক প্রোগ্রামিং অ্যারে dynArr তৈরি করুন
- k := j থেকে n পর্যন্ত লুপ চালান
- le := 0, rg := k-1 থেকে শুরু করে rg < n পর্যন্ত লুপ চালান
- dynArr[le][rg] := INF
- i := le থেকে rg-1 পর্যন্ত (i += j-1) লুপ চালান
- dynArr[le][rg] := min(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]
- 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আউটপুট
31
