Tôi có thể giành chiến thắng trong C ++ không

Giả sử trong một trò chơi có tên "100 trò chơi", hai người chơi thay phiên nhau cộng vào tổng số đang chạy, bất kỳ số nguyên nào từ 1 đến 10. Người chơi đầu tiên làm cho tổng số đang chạy đạt đến hoặc vượt quá 100, anh ấy / cô ấy thắng. Vậy điều gì sẽ xảy ra nếu chúng ta thay đổi trò chơi để người chơi không thể sử dụng lại các số nguyên?

Ví dụ:nếu hai người chơi thay phiên nhau rút ra từ một nhóm các số chung là 1..15 mà không có sự thay thế cho đến khi họ đạt đến tổng số> =100.

Vì vậy, giả sử đưa ra một số nguyên maxChoosableInteger và một số nguyên khác tổng số mong muốn, hãy xác định xem người chơi đầu tiên di chuyển có thể buộc giành chiến thắng hay không, giả sử cả hai người chơi đều chơi tối ưu.

Chúng ta luôn có thể giả định rằng maxChoosableInteger sẽ không lớn hơn giá trị 20 và tổng mong muốn sẽ không lớn hơn 300. Vì vậy, nếu đầu vào là maxChoosableInteger =20 và tổng mong muốn là 11, thì kết quả sẽ là false. Bất kể người chơi đầu tiên chọn, người chơi đầu tiên sẽ thua.

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

• Tạo một mảng có tên dp có kích thước 2 ^ 21

• Xác định phương thức giải quyết (), phương thức này sẽ lấy n, s và mặt nạ.

• nếu s <=0, thì trả về false

• nếu dp [mask] không phải là -1, thì trả về dp [mask]

• đặt ret:=false

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

  • nếu (mặt nạ dịch chuyển I bit sang phải) là lẻ, thì

    • ret:=ret OR (nghịch đảo của giải (n, s - i, mặt nạ XOR 2 ^ i))

• dp [mask]:=ret

• trả lại ret

• Từ phương thức chính, hãy thực hiện như sau

• nếu muốn Tổng <=0, sau đó trả về true

• cho tôi trong phạm vi 0 đến 2 ^ 21

  • dp [i]:=-1

• nếu muốn Tổng> (tổng của n số đầu tiên), sau đó trả về false

• trả về giải quyết (n, wishTotal, 0)

Ví dụ (C ++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int dp[1 << 21];
   bool solve(int n, int s, int mask){
      if(s <= 0) return false;
      if(dp[mask] != -1) return dp[mask];
      bool ret = false;
      for(int i = 1; i <= n; i++){
         if(!((mask >> i) & 1)){
            ret |= (!solve(n, s - i, (mask ^ (1 << i))));
         }
      }
      return dp[mask] = ret;
   }
   bool canIWin(int n, int desiredTotal) {
      if(desiredTotal <= 0) return true;
      for(int i = 0; i < (1 << 21); i++)dp[i] = -1;
      if(desiredTotal > (n * (n + 1)/ 2))return false;
      return solve(n, desiredTotal, 0);
   }
};
main() {
Solution ob;
cout << (ob.canIWin(10,11));
}

Đầu vào

10
11

Đầu ra

0