資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中我能贏嗎
假設在一個名為“100 遊戲”的遊戲中，兩位玩家輪流將任意 1 到 10 之間的整數加到一個執行總和中。第一個使執行總和達到或超過 100 的玩家獲勝。那麼，如果我們更改遊戲規則，使得玩家不能重複使用整數，會發生什麼情況呢？
例如，如果兩位玩家輪流從 1 到 15 的公共數字池中抽取數字（不放回），直到他們達到總和 >= 100。
因此，假設給定一個整數 maxChoosableInteger 和另一個整數 desired total，確定第一個移動的玩家是否可以迫使獲勝，假設兩個玩家都以最佳方式進行遊戲。
我們始終可以假設 maxChoosableInteger 的值不會大於 20，並且 desired total 的值不會大於 300。因此，如果輸入為 maxChooseableInteger = 20，並且 desired total 為 11，則結果將為 false。無論第一個玩家選擇什麼，第一個玩家都會輸。
為了解決這個問題，我們將遵循以下步驟 -
建立一個名為 dp 的大小為 2^21 的陣列
定義一個名為 solve() 的方法，它將接收 n、s 和 mask 作為引數。
如果 s <= 0，則返回 false
如果 dp[mask] 不為 -1，則返回 dp[mask]
設定 ret := false
對於 I 的範圍從 1 到 n
如果（將 mask 向右移動 I 位）為奇數，則
ret := ret OR (solve(n, s – i, mask XOR 2^i) 的反值)
dp[mask] := ret
返回 ret
從主方法中執行以下操作
如果 desiredTotal <= 0，則返回 true
對於 I 的範圍從 0 到 2^21
dp[i] := -1
如果 desiredTotal > (前 n 個數字的總和)，則返回 false
返回 solve(n, desiredTotal, 0)
示例（C++）
讓我們看看下面的實現，以便更好地理解 -
#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));
}輸入
10 11
輸出
0
213 次瀏覽
