โปรแกรมหาคะแนนสูงสุดในเกมหินใน Python

สมมติว่ามีหินหลายก้อนวางเรียงเป็นแถว และหินแต่ละก้อนมีตัวเลขที่เกี่ยวข้องกันซึ่งกำหนดไว้ในอาร์เรย์ stoneValue ในแต่ละรอบ Amal แบ่งแถวออกเป็นสองส่วน จากนั้น Bimal จะคำนวณมูลค่าของแต่ละส่วน ซึ่งเป็นผลรวมของค่าของหินทั้งหมดในส่วนนี้ Bimal ทิ้งส่วนที่มีมูลค่าสูงสุดและคะแนนของ Amal จะเพิ่มขึ้นตามมูลค่าของส่วนที่เหลือ เมื่อค่าของสองส่วนเท่ากัน Bimal ให้ Amal ตัดสินใจว่าส่วนใดที่จะถูกโยนทิ้งไป รอบต่อไปเริ่มต้นด้วยส่วนที่เหลือ เกมจะจบลงเมื่อเหลือหินเพียงก้อนเดียว เราต้องหาคะแนนสูงสุดที่อามาลจะให้ได้

ดังนั้น หากอินพุตเป็นเหมือน stoneValue =[7,3,4,5,6,6] ผลลัพธ์จะเป็น

• ในรอบที่ 1 Amal แบ่งแถวเช่น [7,3,4], [5,6,6] ผลรวมของแถวซ้ายคือ 14 และผลรวมของแถวขวาคือ 17 Bimal โยนแถวขวาทิ้งไป และตอนนี้คะแนนของ Amal เท่ากับ 14

• ในรอบที่ 2 อามาลแบ่งแถวเป็น [7], [3,4] Bimal ทิ้งแถวซ้ายและคะแนนของ Amal จะกลายเป็น (14 + 7) =21

• ในรอบที่ 3 อามาลมีทางเลือกเดียวในการแบ่งแถวคือ [3], [4] Bimal โยนทิ้งแถวขวาและตอนนี้คะแนนของ Amal คือ (21 + 3) =24

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

• กำหนดฟังก์ชัน dfs() นี้จะเริ่ม สิ้นสุด

• ถ้าเริ่มต้น>=สิ้นสุด แล้ว

  • คืนค่า 0

• max_score :=0

• สำหรับการตัดในระยะเริ่มจนจบ ให้ทำ

  • sum1 :=partial_sum[เริ่ม, ตัด]

  • sum2 :=partial_sum[cut+1, end]

  • ถ้า sum1> sum2 แล้ว

    • คะแนน :=sum2 + dfs(cut+1, end)

  • มิฉะนั้นเมื่อ sum1

    • คะแนน :=sum1 + dfs (เริ่ม, ตัด)

  • มิฉะนั้น

    • คะแนน :=sum1 + สูงสุดของ dfs(เริ่ม, คัต) และ dfs(คัต+1, จบ)

  • max_score :=คะแนนสูงสุดและ max_score

• คืนค่า max_score

• กำหนดฟังก์ชัน getPartialSum() นี่จะใช้เวลา

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

  • part_sum[i, i] :=stoneValue[i]

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

  • สำหรับ j ในช่วง i+1 ถึง n - 1 ทำ

    • part_sum[i, j] :=partial_sum[i, j-1] + stoneValue[j]

• จากวิธีหลัก ให้ทำดังนี้

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

• partial_sum :=อาร์เรย์สี่เหลี่ยมจัตุรัสขนาด n x n และเติม 0

• getPartialSum()

• ส่งคืน dfs(0, n-1)

ตัวอย่าง

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

def solve(stoneValue):
   def dfs(start, end):
      if start >= end:
         return 0
      max_score = 0

      for cut in range(start, end):
         sum1 = partial_sum[start][cut]
         sum2 = partial_sum[cut+1][end]
         if sum1 > sum2:
            score = sum2+dfs(cut+1, end)
         elif sum1 < sum2:
            score = sum1+dfs(start, cut)
         else:
            score = sum1+max(dfs(start, cut), dfs(cut+1, end))
            max_score = max(score, max_score)
      return max_score


   def getPartialSum():
      for i in range(n):
         partial_sum[i][i] = stoneValue[i]
      for i in range(n):
         for j in range(i+1, n):
            partial_sum[i][j] = partial_sum[i][j-1]+stoneValue[j]


   n = len(stoneValue)
   partial_sum = [[0]*n for _ in range(n)]
   getPartialSum()
   return dfs(0, n-1)

stoneValue = [7,3,4,5,6,6]
print(solve(stoneValue))

อินพุต

[7,3,4,5,6,6]

ผลลัพธ์

0