โปรแกรมตรวจสอบบุคคลที่ 1 สามารถชนะเกมลูกกวาดโดยทำคะแนนสูงสุดหรือไม่ใน Python

สมมติว่ามีผู้เล่นสองคนกำลังเล่นเกม โดยที่ลูกอมหลายลูกวางเรียงต่อกัน และบุคคลที่ 1 จะได้รับรายการตัวเลขที่เรียกว่า nums ซึ่งแทนค่าคะแนนของลูกกวาดแต่ละลูก ในตาของแต่ละคน พวกเขาสามารถเลือกลูกอมได้ 1, 2 หรือ 3 ลูกจากแถวหน้า จากนั้นลบออกจากรายการ และรับคะแนนรวมที่เพิ่มเข้าไปในคะแนน เกมนี้จะจบลงเมื่อลูกอมทั้งหมดถูกลบและผู้ที่มีคะแนนสูงกว่าจะเป็นผู้ชนะ เราต้องตรวจสอบคนที่ 1 ว่าเกมนี้จะชนะหรือไม่

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[1, 1, 2, 3, 50] ผลลัพธ์จะเป็น True เนื่องจากบุคคลที่ 1 สามารถหยิบลูกอมได้ 1 เม็ด ผู้เล่นอีกคนจะต้องรับลูกอม 1, 2 หรือ 3 เม็ด ไม่ว่ากรณีใด คนที่ 1 สามารถเอาขนมไปในราคา 50 ได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ nums

• table :=อาร์เรย์ที่มี 0 สามตัว

• สำหรับฉันอยู่ในช่วง n − 1 ถึง 0, ลดลง 1 ทำ

  • กำไร :=−inf

  • sum_val :=0

  • สำหรับ j ในช่วง i ถึงขั้นต่ำ i + 3 และ n ทำ

    • sum_val :=sum_val + nums[j]

    • กำไร :=สูงสุดของกำไรและ (sum_val − table[j − i])

  • set table :=รายการที่มีสามค่า [profit, table[0], table[1]]

• คืนค่า จริง เมื่อ table[0]> 0 มิฉะนั้น เท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

import math
class Solution:
   def solve(self, nums):
      n = len(nums)
      table = [0, 0, 0]
      for i in range(n − 1, −1, −1):
         profit = −math.inf
         sum_val = 0
         for j in range(i, min(i + 3, n)):
            sum_val += nums[j]
            profit = max(profit, sum_val − table[j − i])
         table[:] = [profit, table[0], table[1]]
      return table[0] > 0
ob = Solution()
nums = [1, 1, 2, 3, 50]
print(ob.solve(nums))

อินพุต

[1, 1, 2, 3, 50]

ผลลัพธ์

True