C++のストーンゲームII

アリスとボブの2人がいて、石の山でゲームを続けているとします。多数の杭が一列に配置されており、各杭には正の整数の石が配列された杭になっています[i]。ゲームの目的は、ほとんどの石で終了することです。アリスとボブが交代で、アリスが最初に始まります。最初は、M =1です。各プレイヤーのターンで、そのプレイヤーは最初のX個の残りの山（ここでは1 <=X <=2M）のすべての石を取ることができます。次に、M =max（M、X）に設定します。石がなくなるとゲームは終了します。したがって、piles =[2,7,9,4,4]の場合、出力は10になります。これは、アリスが最初に1つのパイルを取得し、次にボブが2つのパイルを取得し、次にアリスが2つのパイルを取得するためです。アリスは手札に合計2+4 + 4=10の山を得ることができます。アリスが最初に2つの山をとる場合、ボブは残っている3つの山すべてをとることができます。この場合、アリスは2 + 7=9パイルを取得します。大きいので10が返されます。

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

• ならば、solveと呼ばれる1つの再帰関数を作成します。これは、配列、i、m、およびdpと呼ばれる1つの行列を取ります。
• i> =arrのサイズの場合、0を返します
• dp [i、m]が-1でない場合は、dp [i、m]を返します
• i – 1 + 2m> =配列のサイズの場合、arr [i]
を返します
• op：=inf
• 1〜2mの範囲のxの場合
  • op：=opの最小値、solve（arr、i + x、xとmの最大値、dp）
• dp [i、m]：=arr [i] – op
• return dp [i、m]
• 実際の方法は次のようになります-
• n：=パイル配列のサイズ、サイズnのarrと呼ばれる1つの配列を作成します
• arr [n-1]：=山[n-1]
• for i：=n –2から0まで
  • arr [i]：=arr [i +1]+パイル[i]
• サイズ（n + 1）x（n + 1）の行列を1つ作成し、これに-1を入力します
• returnsolve（arr、0、1、dp）

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   void printVector(vector <int> v){
      for(int i =0;i<v.size();i++)cout << v[i] << " ";
      cout << endl;
   }
   int stoneGameII(vector<int>& piles) {
      int n = piles.size();
      vector <int> arr(n);
      arr[n-1] = piles[n-1];
      for(int i = n-2;i>=0;i--)arr[i] = arr[i+1] + piles[i];
      vector < vector <int> > dp(n+1,vector <int> (n+1,-1));
      return solve(arr,0,1,dp);
   }
   int solve(vector <int> arr, int i, int m, vector < vector <int> > &dp){
      if(i >=arr.size())return 0;
      if(dp[i][m]!=-1)return dp[i][m];
      if(i-1+2*m >=arr.size())return arr[i];
      int opponentCanTake = INT_MAX;
      for(int x =1;x<=2*m;x++){
         opponentCanTake = min(opponentCanTake,solve(arr,i+x,max(x,m),dp));
      }
      dp[i][m] = arr[i] - opponentCanTake;
      return dp[i][m];
   }
};
main(){
   vector<int> v = {2,7,9,4,4};
   Solution ob;
   cout <<(ob.stoneGameII(v));
}

入力

[2,7,9,4,4]

出力

10