पायथन में ईंट हटाने के खेल का अधिकतम स्कोर खोजने का कार्यक्रम

मान लीजिए अमल और बिमल एक खेल खेल रहे हैं। उनके पास एक सरणी संख्या है जो n ईंटों को इसके शीर्ष पर क्रमांकित के साथ निर्धारित करती है। इस खेल में, खिलाड़ी वैकल्पिक रूप से ऊपर से एक, दो या तीन ईंटों को हटा सकते हैं, और हटाए गए ईंटों पर अंकित अंक उस खिलाड़ी के स्कोर में जोड़ दिए जाते हैं। अगर अमल हमेशा पहले शुरू करता है, तो हमें यह पता लगाना होगा कि अमल अधिकतम कितना स्कोर सुरक्षित करता है।

इसलिए, यदि इनपुट संख्या =[1,2,3,4,5] की तरह है, तो आउटपुट 6 होगा, क्योंकि अमल ईंट {1}, {1,2} या {1,2,3} को हटा सकता है। , यदि अमल पहले दो या तीन तत्वों का चयन करता है, तो बिमल सभी ले सकता है और अधिकतम अंक प्राप्त कर सकता है, लेकिन यदि अमल पहले 1 का चयन करता है, तो बिमल अधिकतम {2,3,4} =9 ले सकता है और अमल 5 ले सकता है, इसलिए कुल अमल का स्कोर 1+5 =6 है।

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

आईएनएफ:=9999
n :=अंकों का आकार
सूची संख्या उलट दें
अस्थायी:=आकार n की एक सरणी और 0 से भरें
कुल:=आकार n की एक सरणी और 0 से भरें
प्रत्येक अनुक्रमणिका i के लिए, और अंकों में मान मान, करें
- कुल[i] :=कुल[i-1] + वैल
अस्थायी[0] :=अंक[0]
अस्थायी[1]:=अस्थायी[0]+संख्या[1]
अस्थायी[2] :=अस्थायी[1]+संख्या[2]
मैं के लिए 3 से n -1 की सीमा में, करो
- a :=nums[i]
- b :=nums[i] + nums[i-1]
- c :=nums[i] + nums[i-1] + nums[i-2]
- temp[i] :=अधिकतम a, b, c
वापसी अस्थायी[n-1]

उदाहरण

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

INF = 99999
def solve(nums):
   n = len(nums)
   nums.reverse()
   temp = [0]*n
   total = [0]*n
   for i, val in enumerate(nums):
      total[i] = total[i-1] + val
   temp[0] = nums[0]
   temp[1] = temp[0]+nums[1]
   temp[2] = temp[1]+nums[2]
   for i in range(3, n):
      a = nums[i]
      b = nums[i] + nums[i-1]
      c = nums[i] + nums[i-1] + nums[i-2]
      temp[i] = max(a, b, c)
   return temp[n-1]

nums = [1,2,3,4,5]
print(solve(nums))

इनपुट

[1,2,3,4,5]