Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm điểm chênh lệch tối thiểu của điểm trò chơi đá bằng Python

Giả sử chúng ta có một mảng được gọi là các viên đá trong đó các viên đá [i] đại diện cho giá trị của viên đá thứ i từ bên trái. Hai người bạn Amal và Bimal đang chơi trò chơi theo lượt với những viên đá này và Amal luôn bắt đầu trước. Có n viên đá được xếp thành một hàng. Mỗi người chơi có thể loại bỏ viên đá ngoài cùng bên trái hoặc viên đá ngoài cùng bên phải khỏi hàng và nhận điểm bằng tổng giá trị của các viên đá còn lại trong hàng. Ai đạt điểm cao hơn sẽ chiến thắng. Bây giờ, Bimal nhận thấy rằng anh ta sẽ luôn thua trò chơi này, vì vậy anh ta quyết định giảm thiểu sự khác biệt của điểm số. Mục tiêu của Amal là tối đa hóa cách biệt về tỷ số. Vì vậy, chúng tôi phải tìm ra sự khác biệt về điểm số của Amal và Bimal nếu cả hai đều chơi tối ưu.

Vì vậy, nếu đầu vào giống như đá =[6,4,2,5,3], thì đầu ra sẽ là 6 vì Amal có thể lấy 3, vì vậy điểm của anh ấy sẽ là 6 + 4 + 2 + 5 =17, điểm của Bimal 0 cho đến nay, và mảng giống như [6,4,2,5], sau đó Bimal lấy 6 nên điểm của anh ta là 4 + 2 + 5 =11, bây giờ mảng là [4,2,5]. Sau đó, Amal loại bỏ 4, vì vậy điểm của anh ấy là 17 + 2 + 5 =24, mảng đá [2,5] Bob loại bỏ 2, do đó điểm của anh ấy 11 + 5 =16, mảng đá hiện tại [5] và Amal loại bỏ đá cuối cùng có giá trị 5 và nhận được 0 điểm, vì vậy điểm cuối cùng của anh ta là 24 + 0 =24. Vì vậy, hiệu số của điểm số của họ là 24-16 =8.

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

  • n:=kích thước của đá
  • dp:=một mảng có kích thước n và điền bằng 0
  • đối với tôi trong phạm vi n - 1 đến 0, giảm đi 1, thực hiện
    • v:=stone [i]
    • run_sum:=0
    • đối với j trong phạm vi i + 1 đến n - 1, thực hiện
      • new_run:=run_sum + stone [j]
      • dp [j]:=(tối đa là new_run - dp [j]) và (run_sum + v - dp [j - 1])
      • run_sum:=new_run
  • trả về dp [n - 1]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

def solve(stones):
   n = len(stones)
   dp = [0] * n

   for i in range(n - 1, -1, -1):
      v = stones[i]
      run_sum = 0

      for j in range(i + 1, n):
         new_run = run_sum+stones[j]
         dp[j] = max(new_run - dp[j], run_sum+v - dp[j - 1])
         run_sum = new_run
   return dp[n - 1]

stones = [6,4,2,5,3]
print(solve(stones))

Đầu vào 

[6,4,2,5,3]

Đầu ra 

8