我可以用C ++赢吗
假设在一个名为“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
对于1到n范围内的I
ret：=retOR（resolve（n，s–i，maskXOR2^i）的反函数）
如果（将掩码I位向右移动）是奇数，则
dp[mask]：=ret
返回ret
在主要方法中，执行以下操作
如果期望总计<=0，则返回true
适用于0到2^21范围内的I
dp[i]：=-1
如果需要合计>（前n个数字的总和），则返回false
返回solve(n,desireTotal,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