数据结构
网络
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 次浏览
