मान लीजिए अमल और बिमल पत्थरों के ढेर से खेल रहे हैं। एक पंक्ति में कई पत्थरों को व्यवस्थित किया गया है, और प्रत्येक पत्थर का एक संबद्ध मूल्य होता है जो कि पत्थर के मूल्य नामक सरणी में दी गई संख्या है।
अमल और बिमल बारी बारी से अमल करते हैं, अमल पहले शुरू करते हैं। प्रत्येक खिलाड़ी की बारी पर, वह पंक्ति में पहले शेष पत्थरों से 1, 2 या 3 पत्थर ले सकता है।
प्रत्येक खिलाड़ी का स्कोर लिए गए पत्थरों के मूल्यों का योग होता है। प्रारंभ में स्कोर 0 है। खेल का लक्ष्य उच्चतम स्कोर के साथ समाप्त करना है, और विजेता उच्चतम स्कोर वाला खिलाड़ी होता है और एक टाई भी हो सकता है। खेल तब तक जारी रहता है जब तक कि सभी पत्थर नहीं ले लिए जाते।
हम मान लेंगे कि अमल और बिमल बेहतर तरीके से खेल रहे हैं। अगर अमल जीतता है तो हमें "अमल" वापस करना होगा, "बिमल" अगर बिमल जीतता है या "टाई" अगर वे समान स्कोर के साथ खेल समाप्त करते हैं।
इसलिए, यदि इनपुट मान =[1,2,3,7] जैसा है, तो आउटपुट बिमल होगा, क्योंकि अमल हमेशा हार जाएगा। उसकी सबसे अच्छी चाल तीन पाइल्स लेने की होगी और स्कोर 6 हो जाएगा। अब बिमल का स्कोर 7 है और बिमल जीत जाता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
आकार n + 10
. के सरणी dp को परिभाषित करें -
आकार n + 10 के एक सरणी योग को परिभाषित करें
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
डीपी [i] :=-(1^9)
-
-
योग [एन -1] =वी [एन -1]
-
इनिशियलाइज़ करने के लिए i :=n - 2, जब i>=0, अपडेट करें (i से 1 घटाएं), −
करें-
योग[i] :=योग[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] और योग[i] - dp[k]
-
-
-
कुल:=योग[0]
-
एक्स:=डीपी [0]
-
y :=कुल - x
-
वापसी x> y सत्य है, तो "अमल":यदि x और y समान हैं तो "टाई" अन्यथा "बिमल"
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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";
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,7};
cout << (ob.stoneGameIII(v));
} इनपुट
{1,2,3,7} आउटपुट
Bimal