सी++ में स्टोन गेम

मान लीजिए कि हमारे पास दो खिलाड़ी एलेक्स और ली हैं, वे पत्थरों के ढेर के साथ एक खेल खेलते हैं। ढेरों की संख्या सम संख्या में होती है जो एक पंक्ति में व्यवस्थित होती हैं, और प्रत्येक ढेर में कुछ संख्या में पत्थरों के ढेर होते हैं [i]। खेल का उद्देश्य सबसे अधिक पत्थरों के साथ समाप्त करना है। जब पत्थरों की कुल संख्या विषम होती है, तो कोई संबंध नहीं होता है। एलेक्स और ली बारी बारी से लेते हैं, एलेक्स पहले शुरू करते हैं। प्रत्येक मोड़ में, एक खिलाड़ी पंक्ति के आरंभ या अंत से पत्थरों का पूरा ढेर लेता है। यह तब तक जारी रहेगा जब तक कोई और ढेर नहीं बचेगा, जिस बिंदु पर सबसे अधिक पत्थरों वाला व्यक्ति जीत जाता है। मान लें कि एलेक्स और ली बेहतर तरीके से खेलते हैं, जांचें कि एलेक्स गेम जीतता है या नहीं। तो अगर इनपुट [5,3,4,5] जैसा है, तो परिणाम सही होगा, जैसा कि एलेक्स ने पहले शुरू किया है, वह केवल पहले 5 या अंतिम 5 ले सकता है। अब अगर वह पहले 5 लेता है, तो कि पंक्ति बन जाती है [3, 4, 5]। यदि ली 3 लेता है, उसके बाद, बोर्ड [4, 5] है, और एलेक्स 10 अंकों के साथ जीतने के लिए 5 लेता है। जब ली अंतिम 5 लेता है, तब बोर्ड [3, 4] होता है, और एलेक्स 9 अंकों के साथ जीतने के लिए 4 लेता है। तो यह इंगित करता है कि पहला 5 लेना एलेक्स के लिए एक विजयी कदम था, उत्तर सत्य है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=पाइल्स ऐरे का आकार

• आकार n x n का मैट्रिक्स dp बनाएं, पूर्व आकार n + 1 नामक एक और सरणी बनाएं

• मेरे लिए 0 से n - 1 की सीमा में

  • पूर्व[i + 1] :=पूर्व[i] + बवासीर[i]

• l के लिए 2 से n की श्रेणी में −

  • i के लिए :=0, j :=l – 1, j

    • dp[i, j] :=अधिकतम बवासीर [j] + पूर्व [j] - पूर्व [i] - dp [i, j - 1] और बवासीर [i] + पूर्व [i + 2] - पूर्व [j] + डीपी [i + 1, जे]

• डीपी [0, एन -1]> डीपी [0, एन -1] - पूर्व [एन] जब सच हो जाता है

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool stoneGame(vector<int>& piles) {
      int n = piles.size();
      vector < vector <int> > dp(n,vector <int>(n));
      vector <int> pre(n + 1);
      for(int i = 0; i < n; i++){
         pre[i + 1] = pre[i] + piles[i];
      }
      for(int l = 2; l <= n; l++){
         for(int i = 0, j = l - 1; j < n; i++, j++){
            dp[i][j] = max(piles[j] + pre[j] - pre[i] - dp[i][j - 1], piles[i] + pre[i + 2] - pre[j] +             dp[i       + 1][j]);
         }
      }
      return dp[0][n - 1] > dp[0][n - 1] - pre[n];
   }
};
main(){
   vector<int> v = {5,3,4,5};
   Solution ob;
   cout << (ob.stoneGame(v));
}

इनपुट

[5,3,4,5]

आउटपुट

1