C ++中的Stone Game III

假设Amal和Bimal正在玩石头堆。一排有几块宝石,每块宝石都有一个关联的值,该值是在数组中指定的名为stoneValue的数字。

Amal和Bimal轮流使用,Amal首先开始。轮到每个玩家时,他/她可以从该行中剩余的第一块石头中拿出1、2或3块石头。

每个玩家的分数是所取石头的总和。最初的分数是0。游戏的目标是以最高分数结束,而获胜者是拥有最高分数的玩家,并且也可能有平局。游戏将一直进行到所有石头都被拿走为止。

我们将假定Amal和Bimal处于最佳状态。如果Amal获胜,我们必须返回“ Amal”,如果Bimal获胜,则必须返回“ Bimal”,如果他们以相同的分数结束游戏,则必须返回“ Tie”。

因此,如果输入值= [1,2,3,7],则输出将为Bimal,因为Amal始终会丢失。他最好的举动是拿下三堆,比分变成6。现在,比马尔的比分是7,比马尔取得了胜利。

为了解决这个问题,我们将遵循以下步骤-

  • 为了解决这个问题,我们将遵循以下步骤-

  • 定义大小为n + 10的数组dp

  • 定义大小为n + 10的数组和

  • 对于初始化i:= 0,当i <n时,更新(将i增加1),执行-

    • 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),-

    • dp [i]:= dp [i]和sum [i]的最大值-dp [k]

    • 对于初始化k:= i + 1,当k <= i + 3并且k <= n时,更新(将k增加1),-

  • 总计:=总和[0]

  • x:= dp [0]

  • y:=总计-x

  • 返回x> y为真,则为“ 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