मान लीजिए हमारे पास गैर-ऋणात्मक पूर्णांकों की एक सरणी है जो स्कोर दर्शाती है। पहला खिलाड़ी सरणी के किसी भी छोर से एक संख्या चुनता है, फिर दूसरा खिलाड़ी, फिर पहला, और इसी तरह। प्रत्येक बार जब कोई खिलाड़ी एक संख्या चुनता है, तो वह संख्या दूसरे खिलाड़ी के लिए उपलब्ध नहीं रहती। यह तब तक चलता है जब तक सभी स्कोर चुने नहीं जाते। जिस खिलाड़ी का कुल स्कोर अधिक होता है, वह जीतता है। हमें भविष्यवाणी करनी है कि क्या खिलाड़ी 1 विजेता है।
उदाहरण के लिए, यदि इनपुट [1, 5, 233, 7] है, तो आउटपुट True होगा, क्योंकि पहला खिलाड़ी 1 चुनता है। दूसरा खिलाड़ी 5 और 7 में से चुनता है। चाहे वह कुछ भी चुने, पहला खिलाड़ी 233 चुन सकता है। अंत में, पहले खिलाड़ी का स्कोर 234 होता है, दूसरे का 12, इसलिए पहला खिलाड़ी जीत सकता है।
हल करने की विधि
हम डायनामिक प्रोग्रामिंग का उपयोग करेंगे:
- यदि n == 1, तो true लौटाएं।
- player1, player2, sum के लिए n x n सरणियां परिभाषित करें।
- सभी को -1 से प्रारंभ करें।
- उप-सरणियों के योग की गणना करें।
- लंबाई 1 से n तक के लिए, सभी उप-सरणियों के लिए इष्टतम चाल की गणना करें।
- अंत में, जांचें कि क्या player1[0][n-1] >= player2[0][n-1] है।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: lli solve(vector <int> arr, lli n){ if (n == 1) return true; lli player1[n][n], player2[n][n], sum[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { player1[i][j] = -1; player2[i][j] = -1; } } for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (i == j) { sum[i][j] = arr[i]; } else { sum[i][j] = arr[j] + sum[i][j - 1]; } } } for (int length = 1; length <= n; length++) { for (int i = 0; i + length - 1 < n; i++) { lli end = i + length - 1; if (i + 1 <= end) player1[i][end] = max(arr[i] + (player2[i + 1][end] == -1 ? 0 : player2[i + 1][end]), arr[end] + (player2[i][end - 1] == -1 ?: player2[i][end - 1])); else player1[i][end] = arr[i]; player2[i][end] = sum[i][end] - player1[i][end]; } } return player1[0][n - 1] >= player2[0][n - 1]; } bool PredictTheWinner(vector<int>& nums) { return solve(nums, nums.size()) ; } }; main(){ Solution ob; vector<int> v = {1, 5, 233, 7}; cout << (ob.PredictTheWinner(v)); }
इनपुट
{1, 5, 233, 7}
आउटपुट
1
