C++의 스톤 게임

<시간/>

Alex와 Lee 두 명의 플레이어가 돌 더미를 가지고 게임을 한다고 가정해 보겠습니다. 짝수 개의 말뚝이 일렬로 배열되어 있고, 각 말뚝에는 몇 개의 돌더미[i]가 있습니다. 게임의 목표는 가장 많은 돌로 끝나는 것입니다. 돌의 총 개수가 홀수이면 동점이 없습니다. Alex와 Lee가 번갈아 가며 Alex가 먼저 출발합니다. 각 턴에서 플레이어는 줄의 시작이나 끝에서 전체 돌 더미를 가져옵니다. 이것은 더 이상 더미가 남지 않을 때까지 계속되며, 그 시점에서 가장 많은 돌을 가진 사람이 승리합니다. Alex와 Lee가 최적으로 플레이한다고 가정하고 Alex가 게임에서 이기는지 확인하세요. 따라서 입력이 [5,3,4,5]와 같으면 결과는 true가 됩니다. Alex가 먼저 시작했기 때문에 그는 처음 5개 또는 마지막 5개만 사용할 수 있습니다. 이제 처음 5개를 사용하면 행은 [3, 4, 5]가 됩니다. Lee가 3을 취하면 그 후 판은 [4, 5]이고 Alex는 5를 취하여 10점으로 승리합니다. Lee가 마지막 5개를 가져가면 보드는 [3, 4]이고 Alex는 4개를 가져와 9점으로 이깁니다. 따라서 이것은 처음 5개를 취하는 것이 Alex에게 승리한 움직임임을 나타냅니다. 대답은 사실입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=파일 배열의 크기
크기가 n x n인 행렬 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]

C++의 스톤 게임

예시

입력

출력