我能用 C++ 赢吗
c++server side programmingprogramming
假设在一个名为"100 游戏"的游戏中，两个玩家轮流将 1 到 10 之间的任意整数加到累计总数中。最先使累计总数达到或超过 100 的玩家获胜。那么如果我们改变游戏，让玩家不能重复使用整数会怎么样呢?
例如，如果两个玩家轮流从公共数字池 1..15 中抽取数字，不重复抽取，直到总数达到 >= 100。
因此，假设给定一个整数 maxChoosableInteger 和另一个整数期望总数，确定第一个移动的玩家是否可以强制获胜，假设两个玩家都发挥最佳。
我们始终可以假设 maxChoosableInteger 不会大于 20 的值，并且期望总数不会大于 300。因此，如果输入是 maxChooseableInteger = 20，并且期望总数是 11，则结果将为 false。无论第一个玩家选择什么，第一个玩家都会输。
为了解决这个问题，我们将遵循以下步骤 −
创建一个名为 dp 的数组，大小为 2^21
定义一个方法solve()，它将采用n、s和mask。
如果s <= 0，则返回false
如果dp[mask]不为-1，则返回dp[mask]
设置ret := false
对于I在1到n的范围内
如果(将掩码I位向右移动)为奇数，则
ret := ret OR(逆解决(n，s – i，mask XOR 2^i))
dp[mask] := ret
return ret
从主方法中，执行以下操作
如果requiredTotal <= 0，则返回 true
对于范围为 0 到 2^21 的 I
dp[i] := -1
如果requiredTotal >(前 n 个数字的总和)，则返回 false
return 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
