C++ में स्टोन गेम III

समस्या विवरण

मान लीजिए अमल और बिमल पत्थरों के ढेर के साथ खेल रहे हैं। कई पत्थर एक पंक्ति में व्यवस्थित हैं, और प्रत्येक पत्थर का एक संबद्ध मान है जो stoneValue नामक सरणी में दी गई संख्या है।

अमल और बिमल बारी-बारी से खेलते हैं, अमल पहले शुरू करता है। प्रत्येक खिलाड़ी की बारी पर, वह पंक्ति में पहले शेष पत्थरों में से 1, 2 या 3 पत्थर ले सकता है।

प्रत्येक खिलाड़ी का स्कोर उसके द्वारा लिए गए पत्थरों के मानों का योग है। प्रारंभ में स्कोर 0 है। खेल का लक्ष्य उच्चतम स्कोर के साथ समाप्त करना है, और विजेता वह खिलाड़ी है जिसका स्कोर सबसे अधिक है और टाई भी हो सकता है। खेल तब तक चलता है जब तक सभी पत्थर ले लिए जाते हैं।

हम मान लेंगे कि अमल और बिमल इष्टतम रूप से खेल रहे हैं। हमें "अमल" लौटाना है यदि अमल जीतता है, "बिमल" यदि बिमल जीतता है या "टाई" यदि वे समान स्कोर के साथ खेल समाप्त करते हैं।

उदाहरण

यदि इनपुट है: values = [1,2,3,7], तो आउटपुट होगा बिमल, क्योंकि अमल हमेशा हार जाएगा। उसकी सर्वश्रेष्ठ चाल तीन ढेर लेना होगी और स्कोर 6 हो जाएगा। अब बिमल का स्कोर 7 है और बिमल जीतता है।

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

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (डायनामिक प्रोग्रामिंग):

• आकार n + 10 का एक सरणी dp परिभाषित करें
• आकार n + 10 का एक सरणी sum परिभाषित करें
• i := 0 से आरंभ करें, जब i < n, i को 1 से बढ़ाते हुए:
  • dp[i] := -1e9
• sum[n - 1] = v[n - 1]
• i := n - 2 से आरंभ करें, जब i >= 0, i को 1 से घटाते हुए:
  • sum[i] := sum[i + 1] + v[i]
• i := n - 1 से आरंभ करें, जब i >= 0, i को 1 से घटाते हुए:
  • k := i + 1 से आरंभ करें, जब k <= i + 3 और k <= n, k को 1 से बढ़ाते हुए:
    • dp[i] := dp[i] और sum[i] - dp[k] का अधिकतम
• total := sum[0]
• x := dp[0]
• y := total - x
• यदि x > y तो "अमल" लौटाएं, यदि x और y समान हैं तो "टाई" अन्यथा "बिमल"

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string stoneGameIII(vector<int>& v) {
        int n = v.size();
        vector<int> dp(n + 10);
        vector<int> sum(n + 10);
        for(int i = 0; i < n; i++) dp[i] = -1e9;
        sum[n - 1] = v[n - 1];
        for(int i = n - 2; i >= 0; i--) sum[i] = sum[i + 1] + v[i];
        for(int i = n - 1; i >= 0; i--) {
            for(int k = i + 1; k <= i + 3 && k <= n; k++) {
                dp[i] = max(dp[i], sum[i] - dp[k]);
            }
        }
        int total = sum[0];
        int x = dp[0];
        int y = total - x;
        return x > y ? "Amal" : x == y ? "Tie" : "Bimal";
    }
};

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

इनपुट

{1,2,3,7}

आउटपुट

Bimal