C++ এ স্টোন গেম

ধরুন আমাদের দুজন খেলোয়াড় অ্যালেক্স এবং লি তারা পাথরের স্তূপ নিয়ে একটি খেলা খেলছে। এক সারিতে সাজানো রয়েছে এমন একটি জোড় সংখ্যক পাইল, এবং প্রতিটি স্তূপে কিছু সংখ্যক পাথরের স্তূপ রয়েছে[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 জন্য

  • pre[i + 1] :=pre[i] + piles[i]

• 2 থেকে n −

  পরিসরে l এর জন্য

  • i এর জন্য :=0, j :=l – 1, j

    • dp[i, j] :=পাইলসের সর্বোচ্চ [j] + pre[j] – pre[i] – dp[i, j – 1] এবং piles[i] + pre[i + 2] – pre[j] + dp[i + 1, j]

• dp[0, n – 1]> dp[0, n – 1] – pre[n]

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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