我可以用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：= ret OR（resolve（n，s – i，mask XOR 2 ^ 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