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