C ++で勝つことはできますか？

「100ゲーム」と呼ばれるゲームで、2人のプレーヤーが交代で、1から10までの整数を現在の合計に追加するとします。 100を超えると、彼/彼女が勝ちます。では、プレーヤーが整数を再利用できないようにゲームを変更したらどうなるでしょうか？

たとえば、2人のプレーヤーが交代で、合計> =100に達するまで、交換せずに1..15の共通のプールから抽選を行う場合。

したがって、整数maxChoosableIntegerと別の整数の希望する合計が与えられたとすると、両方のプレーヤーが最適にプレーすると仮定して、最初に移動したプレーヤーが勝利を強制できるかどうかを判断します。

maxChoosableIntegerは値20を超えず、目的の合計は300を超えないと常に想定できます。したがって、入力がmaxChooseableInteger =20で、目的の合計が11の場合、結果はfalseになります。最初のプレーヤーが選択しても、最初のプレーヤーは負けます。

これを解決するには、次の手順に従います-

• サイズ2^21

  のdpという配列を作成します

• メソッドsolve（）を定義します。これには、n、s、およびマスクが必要です。

• s <=0の場合、falseを返します

• dp [mask]が-1でない場合は、dp [mask]

  を返します。

• set ret：=false

• 1からnの範囲のIの場合

  • （マスクを1ビット右にシフトする）が奇数の場合、

    • ret：=ret OR（solve（n、s – i、mask XOR 2 ^ i）の逆）

• dp [マスク]：=ret

• retを返す

• メインの方法から、次のようにします

• 必要に応じてTotal<=0の場合、trueを返します

• 0から2^21の範囲のIの場合

  • dp [i]：=-1

• 必要に応じてTotal>（最初の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