C++에서 이길 수 있습니까?

"100 게임"이라는 게임에서 두 명의 플레이어가 교대로 누계에 1에서 10 사이의 정수를 더한다고 가정합니다. 누계가 처음에 도달하거나 100을 초과하면 그/그녀가 이깁니다. 플레이어가 정수를 재사용할 수 없도록 게임을 변경하면 어떻게 될까요?

예를 들어, 두 플레이어가 총>=100에 도달할 때까지 교체 없이 1..15의 공통 숫자 풀에서 교대로 뽑는 경우

따라서 정수 maxChoosableInteger와 원하는 다른 정수 합계가 있다고 가정하고 두 플레이어가 최적의 상태로 플레이한다고 가정할 때 첫 번째 플레이어가 이동하여 승리할 수 있는지 확인합니다.

maxChoosableInteger가 20보다 크지 않고 원하는 합계가 300보다 크지 않을 것이라고 항상 가정할 수 있습니다. 따라서 입력이 maxChooseableInteger =20이고 원하는 합계가 11인 경우 결과는 거짓이 될 것입니다. 첫 번째 플레이어가 선택하더라도 첫 번째 플레이어는 패배합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

크기가 2^21인 dp라는 배열을 만듭니다.
solve() 메서드를 정의하면 n, s 및 마스크가 필요합니다.
s <=0이면 false를 반환합니다.
dp[마스크]가 -1이 아니면 dp[마스크]
를 반환합니다.
설정 ret :=false
범위 1에서 n까지의 I에 대해
- (마스크 I 비트를 오른쪽으로 이동)이 홀수이면
  - ret :=ret OR (solve(n, s – i, 마스크 XOR 2^i)의 역)
dp[마스크] :=ret
리턴 렛
기본 방법에서 다음을 수행하십시오.
desiredTotal <=0이면 true를 반환합니다.
0에서 2^21 사이의 I에 대해
- dp[i] :=-1
DesiredTotal> (처음 n개의 숫자의 합)인 경우 false를 반환합니다.
해결 반환(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

C++에서 이길 수 있습니까?

예시(C++)

입력

출력