Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

पत्थरों को मर्ज करने की न्यूनतम लागत C++ में

मान लीजिए हमारे पास N पत्थरों के ढेर एक पंक्ति में व्यवस्थित हैं। यहां i-वां ढेर में stones[i] पत्थर हैं। एक चाल में K लगातार ढेरों को एक ढेर में मिलाया जाता है, इस चाल की लागत इन K ढेरों में पत्थरों की कुल संख्या के बराबर होती है। हमें सभी पत्थरों को एक ढेर में मिलाने की न्यूनतम लागत ढूंढनी है। यदि ऐसा कोई समाधान नहीं है, तो -1 वापस करें।

उदाहरण के लिए, यदि इनपुट [3,2,4,1] है और K = 2, तो आउटपुट 20 होगा, क्योंकि हम [3, 2] को 5 की लागत से मिलाते हैं, फिर [4, 1] को 5 की लागत से, और अंत में [5, 5] को 10 की लागत से। कुल लागत 20 है।

हल करने का दृष्टिकोण

यह एक क्लासिक इंटरवल डीपी समस्या है:

  • यदि (n-1) % (k-1) != 0, तो मर्ज करना असंभव है, -1 वापस करें

  • त्वरित रेंज योग क्वेरी के लिए प्रीफिक्स योग सरणी की गणना करें

  • dp[i][j] = अंतराल [i, j] को वैध ढेरों में मर्ज करने की न्यूनतम लागत

  • लंबाई k से n तक के अंतराल के लिए पुनरावृति करें

  • चरण (k-1) में संभावित मध्य बिंदुओं का प्रयास करें

  • जब (j-i) % (k-1) == 0, वर्तमान मर्ज की लागत जोड़ें

उदाहरण

#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]; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {3,2,4,1}; 
    cout << (ob.mergeStones(v, 2)); 
    return 0;
}

इनपुट

{3,2,4,1}, 2

आउटपुट

20
  1. C++ में कार्टेशियन निर्देशांकों को जोड़ने की न्यूनतम लागत ज्ञात करने का प्रोग्राम C++ में कार्टेशियन निर्देशांकों को जोड़ने की न्यूनतम लागत ज्ञात करने का प्रोग्राम

    मान लीजिए हमारे पास 2D कार्टेशियन निर्देशांक बिंदुओं (x, y) की एक सूची है। हम (x0, y0) और (x1, y1) को जोड़ सकते हैं, जिसकी लागत |x0 - x1| + |y0 - y1| है। यदि हमें किसी भी संख्या में बिंदुओं को जोड़ने की अनुमति है, तो हमें वह न्यूनतम लागत ज्ञात करनी होगी जिससे हर बिंदु एक पथ से जुड़ा हो।उदाहरण के लिए

  1. C++ में बोर्ड को वर्गों में काटने की न्यूनतम लागत C++ में बोर्ड को वर्गों में काटने की न्यूनतम लागत

    अवधारणा मान लीजिए लंबाई p और चौड़ाई q का एक बोर्ड दिया गया है, हमें इस बोर्ड को p*q वर्गों में तोड़ना है ताकि तोड़ने की लागत न्यूनतम हो। इस बोर्ड के लिए, प्रत्येक किनारे के लिए काटने की लागत दी जाएगी। संक्षेप में, हमें काटने का ऐसा क्रम चुनना है जिससे लागत न्यूनतम हो। उदाहरण उपरोक्त बोर्ड को वर्गो

  1. C++ में न्यूनतम नाइट मूव्स C++ में न्यूनतम नाइट मूव्स

    मान लीजिए हमारे पास एक अनंत शतरंज बोर्ड है जिसके कोऑर्डिनेट्स -इनफिनिटी से +इनफिनिटी तक हैं, और हमारे पास [0, 0] स्क्वायर पर एक नाइट है। नाइट के 8 संभावित मूव्स होते हैं, जैसा कि नीचे दिखाया गया है। प्रत्येक मूव कार्डिनल डायरेक्शन में दो स्क्वायर, फिर ऑर्थोगोनल डायरेक्शन में एक स्क्वायर होता है। ह