Trò chơi Stone trong C ++

Giả sử chúng ta có hai người chơi Alex và Lee, họ chơi trò chơi với hàng đống đá. Có một số cọc chẵn được xếp thành một hàng, và mỗi cọc có một số đống đá [i]. Mục tiêu của trò chơi là kết thúc với nhiều đá nhất. Khi tổng số đá là số lẻ, không có mối quan hệ nào. Alex và Lee thay phiên nhau, Alex bắt đầu trước. Trong mỗi lượt, một người chơi lấy toàn bộ đống đá từ đầu hoặc cuối hàng. Việc này sẽ được tiếp tục cho đến khi không còn cọc nữa, lúc này người nào có nhiều đá nhất sẽ thắng. Giả sử rằng Alex và Lee chơi tối ưu, hãy kiểm tra xem Alex có thắng trò chơi hay không. Vì vậy, nếu đầu vào là [5,3,4,5], thì kết quả sẽ là true, vì Alex đã bắt đầu trước, anh ấy chỉ có thể lấy 5 đầu tiên hoặc 5 cuối cùng. Bây giờ nếu anh ta lấy 5 đầu tiên, vậy mà hàng đó trở thành [3, 4, 5]. Nếu Lee lấy 3, sau đó bàn cờ là [4, 5], và Alex lấy 5 để giành chiến thắng với 10 điểm. Khi Lee lấy 5 lá cuối cùng, thì bảng là [3, 4], và Alex lấy 4 để giành chiến thắng với 9 điểm. Vì vậy, điều này cho thấy rằng thực hiện 5 bước đầu tiên là một nước đi chiến thắng đối với Alex, câu trả lời là đúng.

Để 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 mảng cọc

• tạo ma trận dp có kích thước n x n, tạo một mảng khác được gọi là trước kích thước n + 1

• cho tôi trong phạm vi từ 0 đến n - 1

  • pre [i + 1]:=pre [i] + cọc [i]

• cho l trong phạm vi 2 đến n -

  • đối với i:=0, j:=l - 1, j

    • dp [i, j]:=max của cọc [j] + pre [j] - pre [i] - dp [i, j - 1] và cọc [i] + pre [i + 2] - pre [j] + dp [i + 1, j]

• trả về true khi dp [0, n - 1]> dp [0, n - 1] - pre [n]

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool stoneGame(vector<int>& piles) {
      int n = piles.size();
      vector < vector <int> > dp(n,vector <int>(n));
      vector <int> pre(n + 1);
      for(int i = 0; i < n; i++){
         pre[i + 1] = pre[i] + piles[i];
      }
      for(int l = 2; l <= n; l++){
         for(int i = 0, j = l - 1; j < n; i++, j++){
            dp[i][j] = max(piles[j] + pre[j] - pre[i] - dp[i][j - 1], piles[i] + pre[i + 2] - pre[j] +             dp[i       + 1][j]);
         }
      }
      return dp[0][n - 1] > dp[0][n - 1] - pre[n];
   }
};
main(){
   vector<int> v = {5,3,4,5};
   Solution ob;
   cout << (ob.stoneGame(v));
}

Đầu vào

[5,3,4,5]

Đầu ra

1