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

Giả sử có một số viên đá được đặt trong một hàng và mỗi viên đá này có một số liên quan được đưa ra trong một mảng stoneValue. Trong mỗi vòng, Amal chia hàng thành hai phần sau đó Bimal tính giá trị của mỗi phần là tổng giá trị của tất cả các viên đá trong phần này. Bimal ném đi phần có giá trị lớn nhất và điểm của Amal tăng theo giá trị của phần còn lại. Khi giá trị của hai phần giống nhau, Bimal để cho Amal quyết định phần nào sẽ bị vứt bỏ. Vòng tiếp theo bắt đầu với phần còn lại. Trò chơi kết thúc khi chỉ còn một viên đá. Chúng ta phải tìm ra số điểm tối đa mà Amal có thể nhận được.

Vì vậy, nếu đầu vào giống như stoneValue =[7,3,4,5,6,6], thì đầu ra sẽ là

Ở vòng 1, Amal chia hàng như [7,3,4], [5,6,6]. Tổng của hàng bên trái là 14 và tổng của hàng phải là 17. Số thập phân ném đi hàng bên phải và điểm của Amal bây giờ là 14.
Tại vòng 2, Amal chia hàng cho [7], [3,4]. Vì vậy, Bimal ném đi hàng bên trái và điểm của Amal trở thành (14 + 7) =21.
Tại vòng 3, Amal chỉ có một sự lựa chọn để chia hàng đó là [3], [4]. Bimal ném ra hàng bên phải và điểm của Amal bây giờ là (21 + 3) =24.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Định nghĩa một hàm dfs (). Quá trình này sẽ bắt đầu, kết thúc
nếu start> =end thì
- trả về 0
max_score:=0
để cắt giảm phạm vi bắt đầu đến kết thúc, hãy thực hiện
- sum1:=part_sum [bắt đầu, cắt]
- sum2:=part_sum [cut + 1, end]
- nếu sum1> sum2 thì
  - điểm:=sum2 + dfs (cắt + 1, kết thúc)
- ngược lại khi sum1
  - điểm:=sum1 + dfs (bắt đầu, cắt)
- nếu không,
  - điểm:=sum1 + tối đa của dfs (bắt đầu, cắt) và dfs (cắt + 1, kết thúc)
- max_score:=tối đa của điểm và max_score
trả về max_score
Định nghĩa một hàm getPartialSum (). Điều này sẽ mất
đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện
- part_sum [i, i]:=stoneValue [i]
đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện
- đối với j trong phạm vi i + 1 đến n - 1, thực hiện
  - part_sum [i, j]:=part_sum [i, j-1] + stoneValue [j]
Từ phương thức chính, hãy thực hiện như sau
n:=kích thước của stoneValue
part_sum:=Một mảng hình vuông có kích thước n x n và được lấp đầy bởi 0
getPartialSum ()
trả về dfs (0, n-1)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để 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]

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

Ví dụ

Đầu vào

Đầu ra