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

アマルとビマルが石の山で遊んでいるとしましょう。いくつかの石が一列に並んでおり、各石には、stoneValueと呼ばれる配列で指定された数値である値が関連付けられています。

AmalとBimalが交代で、Amalが最初に開始します。各プレイヤーのターンで、彼/彼女は列の最初の残りの石から1、2、または3つの石を取ることができます。

各プレイヤーのスコアは、取った石の値の合計です。最初のスコアは0です。ゲームの目標は最高スコアで終了することであり、勝者は最高スコアのプレーヤーであり、同点になる可能性もあります。ゲームはすべての石が奪われるまで続きます。

AmalとBimalが最適にプレイしていると仮定します。アマルが勝った場合は「アマル」、ビマルが勝った場合は「ビマル」、同じスコアでゲームを終了した場合は「タイ」を返す必要があります。

したがって、入力がvalues =[1,2,3,7]のような場合、出力はBimalになります。これは、Amalが常に負けるためです。彼の最善の策は、3つの山を取り、スコアが6になることです。これで、Bimalのスコアは7になり、Bimalが勝ちます。

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

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

• サイズn+10の配列dpを定義します

• サイズn+10の配列の合計を定義します

• 初期化i：=0の場合、i

  • dp [i]：=-（1 ^ 9）

• sum [n-1] =v [n-1]

• 初期化i：=n-2の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • sum [i]：=sum [i + 1] + v [i]

• 初期化i：=n --1の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • 初期化k：=i + 1の場合、k <=i+3およびk<=nの場合、更新（kを1増やします）、実行-

    • dp [i]：=dp[i]とsum[i]の最大値-dp[k]

• 合計：=合計[0]

• x：=dp [0]

• y：=合計-x

• x> yがtrueの場合、「Amal」を返します。xとyが同じ場合は「Tie」、それ以外の場合は「Bimal」

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string stoneGameIII(vector<int>& v) {
      int n = v.size();
      vector <int> dp(n + 10);
      vector <int> sum(n + 10);
      for(int i = 0; i < n; i++)dp[i] = -1e9;
      sum[n - 1] = v[n - 1];
      for(int i = n - 2; i >= 0; i--)sum[i] = sum[i + 1] + v[i];
      for(int i = n- 1 ; i >= 0; i--){
         for(int k = i + 1; k <= i + 3 && k <= n; k++){
            dp[i] = max(dp[i], sum[i] - dp[k]);
         }
      }
      int total = sum[0];
      int x = dp[0];
      int y = total - x;
      return x > y? "Amal" : x == y ? "Tie" : "Bimal";
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,7};
   cout << (ob.stoneGameIII(v));
}

入力

{1,2,3,7}

出力

Bimal