Amal과 Bimal이 돌 더미를 가지고 놀고 있다고 가정합니다. 여러 개의 스톤이 일렬로 배열되어 있으며 각 스톤에는 StoneValue라는 배열에 지정된 숫자인 관련 값이 있습니다.
Amal과 Bimal이 번갈아가며 Amal을 먼저 시작합니다. 각 플레이어의 차례에 해당 행에 남아 있는 첫 번째 돌에서 1, 2 또는 3개의 돌을 가져올 수 있습니다.
각 플레이어의 점수는 가져온 스톤 값의 합계입니다. 처음에 점수는 0입니다. 게임의 목표는 가장 높은 점수로 끝나는 것이며 승자는 가장 높은 점수를 얻은 플레이어이며 동점이 될 수도 있습니다. 게임은 모든 스톤을 차지할 때까지 계속됩니다.
우리는 Amal과 Bimal이 최적의 플레이를 하고 있다고 가정할 것입니다. Amal이 이기면 "Amal", Bimal이 이기면 "Bimal", 같은 점수로 게임을 끝내면 "Tie"를 반환해야 합니다.
따라서 입력이 값 =[1,2,3,7]과 같으면 출력은 Bimal이 되고 As Amal은 항상 잃게 됩니다. 그의 최선의 움직임은 3개의 더미를 가져가서 점수가 6이 되는 것입니다. 이제 Bimal의 점수는 7이고 Bimal이 이깁니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n + 10 크기의 배열 dp 정의
-
크기 n + 10의 배열 합계 정의
-
initialize i :=0의 경우, i
-
dp[i] :=-(1^9)
-
-
합계[n - 1] =v[n - 1]
-
initialize i :=n - 2의 경우 i>=0일 때 업데이트(i를 1만큼 감소), −
-
합계[i] :=합계[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
-
return 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