C++ में पूर्णांकों की सरणी को एकल मान में मर्ज करने की लागत ज्ञात करने का प्रोग्राम

मान लीजिए हमें एक सरणी arr दी गई है जिसमें 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) शून्य के बराबर नहीं है, तो -1 लौटाएं
आकार n+1 का एक सरणी temp परिभाषित करें
i := n-1 से 0 तक:
- temp[i] := arr[i] + temp[i + 1]
आकार n x n का एक 2D सरणी dynArr परिभाषित करें
- k := j से n तक:
  - le := 0, rg := k - 1 से शुरू करते हुए rg < n तक:
    - dynArr[le][rg] := INF
    - i := le से rg-1 तक, चरण 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