ধরুন অমল আর বিমল পাথরের স্তূপ নিয়ে খেলছে। একটি সারিতে সাজানো বেশ কয়েকটি পাথর রয়েছে এবং প্রতিটি পাথরের একটি সম্পর্কিত মান রয়েছে যা অ্যারেতে দেওয়া একটি সংখ্যা যাকে stoneValue বলা হয়।
অমল ও বিমল পালা করে, অমল প্রথমে শুরু করে। প্রতিটি খেলোয়াড়ের পালাক্রমে, সে সারির প্রথম অবশিষ্ট পাথর থেকে 1, 2 বা 3টি পাথর নিতে পারে।
প্রতিটি খেলোয়াড়ের স্কোর হল নেওয়া পাথরের মানের সমষ্টি। প্রাথমিকভাবে স্কোর 0। খেলার লক্ষ্য হল সর্বোচ্চ স্কোর দিয়ে শেষ করা, এবং বিজয়ী হল সর্বোচ্চ স্কোর সহ খেলোয়াড় এবং একটি টাইও হতে পারে। সমস্ত পাথর নেওয়া না হওয়া পর্যন্ত খেলা চলতে থাকে।
আমরা ধরে নেব যে অমল ও বিমল ভালো খেলছে। অমল জিতলে আমাদের "আমল", বিমল জিতলে "বিমল" বা একই স্কোর দিয়ে খেলা শেষ হলে "টাই" করতে হবে।
সুতরাং, যদি ইনপুটটি মানগুলির মত হয় =[1,2,3,7], তাহলে আউটপুট হবে Bimal, As Amal সর্বদা হারাতে হবে। তার সেরা পদক্ষেপ হবে তিনটি পাইল নেওয়া এবং স্কোর 6 হবে। এখন বিমলের স্কোর 7 এবং বিমল জিতেছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n + 10
আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন -
n + 10
আকারের একটি অ্যারের যোগফল সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=0, যখন i
-
dp[i] :=-(1^9)
-
-
যোগফল[n - 1] =v[n - 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]
-
x :=dp[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
