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

アレックスとリーの2人のプレーヤーが、石の山でゲームをしているとします。偶数の杭が一列に並んでおり、各杭にはいくつかの石の杭があります[i]。ゲームの目的は、ほとんどの石で終了することです。石の総​​数が奇数の場合、同点はありません。アレックスとリーが交代で、アレックスが最初に始まります。各ターンで、プレイヤーは列の最初または最後から石の山全体を取ります。これは、山がなくなるまで続けられ、その時点で、最も多くの石を持っている人が勝ちます。アレックスとリーが最適にプレーしていると仮定して、アレックスがゲームに勝つかどうかを確認します。したがって、入力が[5,3,4,5]の場合、結果はtrueになります。これは、Alexが最初に開始したため、最初の5または最後の5しか取得できないためです。行が[3、4、5]になります。その後、リーが3を取ると、ボードは[4、5]になり、アレックスは5を取り、10ポイントで勝ちます。リーが最後の5を取るとき、ボードは[3、4]であり、アレックスは9ポイントで勝つために4を取ります。つまり、これは最初の5つを取ることがアレックスにとって勝利の動きだったことを示しています。答えは正しいです。

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

• n：=杭配列のサイズ

• サイズnxnの行列dpを作成し、サイズn+1のpreという別の配列を作成します

• 0からn–1の範囲のiの場合

  • pre [i + 1]：=pre[i]+パイル[i]

• 2からnの範囲のlの場合-

  • i：=0、j：=l – 1、j

    • dp [i、j]：=最大の杭[j] + pre [j] – pre [i] – dp [i、j –1]および杭[i]+ pre [i + 2] – pre [j] + dp [i + 1、j]

• dp [0、n – 1]> dp [0、n – 1] – pre [n]

  の場合にtrueを返します

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool stoneGame(vector<int>& piles) {
      int n = piles.size();
      vector < vector <int> > dp(n,vector <int>(n));
      vector <int> pre(n + 1);
      for(int i = 0; i < n; i++){
         pre[i + 1] = pre[i] + piles[i];
      }
      for(int l = 2; l <= n; l++){
         for(int i = 0, j = l - 1; j < n; i++, j++){
            dp[i][j] = max(piles[j] + pre[j] - pre[i] - dp[i][j - 1], piles[i] + pre[i + 2] - pre[j] +             dp[i       + 1][j]);
         }
      }
      return dp[0][n - 1] > dp[0][n - 1] - pre[n];
   }
};
main(){
   vector<int> v = {5,3,4,5};
   Solution ob;
   cout << (ob.stoneGame(v));
}

入力

[5,3,4,5]

出力

1