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

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

เช่น ถ้าอินพุตคือ stoneValue = [7,3,4,5,6,6] ผลลัพธ์จะเป็น:

• รอบ 1: Amal แบ่งเป็น [7,3,4], [5,6,6] ผลรวมซ้าย 14 ขวา 17 Bimal ทิ้งขวา คะแนน Amal = 14
• รอบ 2: Amal แบ่งเป็น [7], [3,4] Bimal ทิ้งซ้าย คะแนน Amal = 14 + 7 = 21
• รอบ 3: Amal แบ่งเป็น [3], [4] Bimal ทิ้งขวา คะแนน Amal = 21 + 3 = 24

วิธีแก้ปัญหา

• กำหนดฟังก์ชัน dfs() รับ start, end:
  • ถ้า start >= end: return 0
  • max_score := 0
  • สำหรับ cut ในช่วง start ถึง end:
    • sum1 := partial_sum[start, cut]
    • sum2 := partial_sum[cut+1, end]
    • ถ้า sum1 > sum2: score := sum2 + dfs(cut+1, end)
    • มิฉะนั้นถ้า sum1 < sum2: score := sum1 + dfs(start, cut)
    • มิฉะนั้น: score := sum1 + max(dfs(start, cut), dfs(cut+1, end))
    • max_score := max(score, max_score)
  • return max_score
• กำหนดฟังก์ชัน getPartialSum():
  • สำหรับ i ในช่วง 0 ถึง n - 1: partial_sum[i, i] := stoneValue[i]
  • สำหรับ i ในช่วง 0 ถึง n - 1:
    • สำหรับ j ในช่วง i+1 ถึง n - 1: partial_sum[i, j] := partial_sum[i, j-1] + stoneValue[j]
• จากเมธอดหลัก:
  • n := ขนาดของ stoneValue
  • partial_sum := อาร์เรย์สี่เหลี่ยมขนาด n x n เติม 0
  • getPartialSum()
  • return 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