Tôi Có Thể Thắng Được Không Trong C++

Giả sử trong trò chơi "100 game", hai người chơi lần lượt thêm vào tổng chung bất kỳ số nguyên từ 1 đến 10. Người nào làm tổng đạt hoặc vượt 100 trước thắng. Nếu thay đổi quy tắc: người chơi không thể tái sử dụng các số đã chọn?

Ví dụ, hai người chơi lần lượt lấy từ kho số 1..15 không lặp lại cho đến khi tổng >= 100.

Cho maxChoosableInteger và desiredTotal, xác định người chơi đầu tiên có thể buộc thắng không, giả sử cả hai chơi tối ưu. maxChoosableInteger ≤ 20, desiredTotal ≤ 300. Ví dụ: maxChoosableInteger = 20, desiredTotal = 11, kết quả false. Dù người đầu chọn gì, họ đều thua.

Để giải quyết, chúng ta làm theo các bước:

• Tạo mảng dp kích thước 2^21.

• Định nghĩa phương thức solve(n, s, mask):

  • Nếu s <= 0, trả về false.

  • Nếu dp[mask] != -1, trả về dp[mask].

  • ret := false.

  • Với i từ 1 đến n: nếu bit i của mask là 0 (chưa dùng), ret |= !solve(n, s-i, mask ^ (1<

  • dp[mask] = ret, trả về ret.

• Từ phương thức chính: nếu desiredTotal <= 0 trả về true; khởi tạo dp = -1; nếu desiredTotal > tổng n số đầu tiên, trả về false; gọi solve(n, desiredTotal, 0).

Ví dụ (C++)

Hãy xem 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);
    }
};

int main() {
    Solution ob;
    cout << (ob.canIWin(10,11));
}

Đầu vào

10 11

Đầu ra

0