Chương trình tìm điểm tối đa trong trò chơi đá trong Python

Có đá xếp hàng, mỗi viên có giá trị stoneValue. Mỗi vòng Amal chia hàng thành 2 phần, Bimal tính tổng mỗi phần. Bimal bỏ phần tổng lớn hơn, Amal được điểm = phần còn lại. Nếu bằng nhau Amal chọn. Tiếp tục với phần còn lại. Kết thúc khi còn 1 viên. Tìm điểm tối đa Amal.

Ví dụ: stoneValue = [7,3,4,5,6,6], đầu ra = 24 (chi tiết trong bài).

Giải pháp

Interval DP với memoization:

• dfs(start, end): trả về điểm tối đa từ đoạn [start, end]
• Nếu start >= end: trả về 0
• max_score := 0
• Với cut từ start đến end-1:
  • sum1 := partial_sum[start][cut], sum2 := partial_sum[cut+1][end]
  • Nếu sum1 > sum2: score = sum2 + dfs(cut+1, end)
  • Nếu sum1 < sum2: score = sum1 + dfs(start, cut)
  • Nếu bằng: score = sum1 + max(dfs(start,cut), dfs(cut+1,end))
  • max_score = max(max_score, score)
• Trả về max_score
• Tính trước partial_sum[i][j] = tổng stoneValue[i..j]
• Gọi dfs(0, n-1)

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

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))

Đầu vào

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

Đầu ra

24