C++で勝者を予測する

非負の整数であるスコアの配列があるとします。最初のプレーヤーは、配列のいずれかの端から番号の1つを選択し、次に2番目のプレーヤー、次に最初のプレーヤーというように選択します。プレーヤーが番号を選択するたびに、その番号は他のプレーヤーが利用できなくなります。これは、すべてのスコアが選択されるまで続きます。最大スコアを獲得したプレイヤーが勝ちます。したがって、スコア配列がある場合は、プレーヤー1が勝者であるかどうかを予測する必要があります。

したがって、入力が[1、5、233、7]の場合、最初のプレーヤーが1を選択したため、出力はTrueになります。次に、2番目のプレーヤーは5から7のいずれかを選択する必要があります。プレーヤーが選択すると、最初のプレーヤーは233を選択できます。最後に、最初のプレーヤーは2番目のプレーヤー（12）よりもスコア（234）が多いため、最初のプレーヤーが勝つことができるため、trueを返す必要があります。

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

• nが1と同じ場合、-

  • trueを返す

• サイズがnxnのアレイplayer1、サイズn x nのアレイplayer2、およびサイズnxnの合計を定義します。

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

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

    • player1 [i、j]：=-1

    • player2 [i、j]：=-1

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

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

    • iがjと同じ場合、-

      • sum [i、j]：=arr [i]

    • それ以外の場合

      • sum [i、j]：=arr [j] + sum [i、j-1]

• 長さの初期化：=1の場合、長さ<=nの場合、更新（長さを1増やします）、実行-

  • 初期化i：=0の場合、i+長さ-1

    • 終了：=i+長さ-1

    • i + 1 <=終了の場合、-

      • player1 [i、end]：=最大arr [i] +（（player2 [i + 1、end]が-1と同じ場合は0、それ以外の場合はplayer2 [i + 1、end]））およびarr [end ] +（（player2 [i、end-1]が-1と同じ場合、それ以外の場合、player2 [i、end-1]））

    • それ以外の場合

      • player1 [i、end]：=arr [i]

    • player2 [i、end]：=sum [i、end]-player1 [i、end]

• player1 [0、n --1]> =player2 [0、n -1]の場合はtrueを返し、それ以外の場合はfalseを返します

例

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

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   lli solve(vector <int> arr, lli n){
      if (n == 1)
         return true;
      lli player1[n][n], player2[n][n], sum[n][n];
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            player1[i][j] = -1;
            player2[i][j] = -1;
         }
      }
      for (int i = 0; i < n; i++) {
         for (int j = i; j < n; j++) {
            if (i == j) {
               sum[i][j] = arr[i];
            }
            else {
               sum[i][j] = arr[j] + sum[i][j - 1];
            }
         }
      }
      for (int length = 1; length <= n; length++) {
         for (int i = 0; i + length - 1 < n; i++) {
            lli end = i + length - 1;
            if (i + 1 <= end)
               player1[i][end] = max(arr[i] + (player2[i + 1][end] == -1 ? 0 : player2[i + 1][end]), arr[end] + (player2[i][end - 1] == -1 ?: player2[i][end - 1]));
            else
               player1[i][end] = arr[i];
               player2[i][end] = sum[i][end] - player1[i][end];
            }
         }
         return player1[0][n - 1] >= player2[0][n - 1];
      }
      bool PredictTheWinner(vector<int>& nums) {
         return solve(nums, nums.size()) ;
   }
};
main(){
   Solution ob;
   vector<int> v = {1, 5, 233, 7};
   cout << (ob.PredictTheWinner(v));
}

入力

{1, 5, 233, 7}

出力

1