数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++石头游戏 III
假设Amal和Bimal正在玩一堆石头游戏。几块石头排成一排，每块石头都有一个关联值，该值是在名为stoneValue的数组中给出的数字。
Amal和Bimal轮流取石头，Amal先开始。在每个玩家的回合中，他/她可以从排在最前面的剩余石头中取走1、2或3块石头。
每个玩家的分数是所取石头的值的总和。最初分数为0。游戏的目标是以最高分结束，得分最高的玩家获胜，也可能出现平局。游戏持续到所有石头都被取走为止。
我们将假设Amal和Bimal都在最佳状态下游戏。如果Amal获胜，我们必须返回“Amal”；如果Bimal获胜，返回“Bimal”；如果他们以相同的分数结束游戏，则返回“Tie”。
因此，如果输入类似于values = [1,2,3,7]，则输出将是Bimal，因为Amal总是会输。他最好的举动是拿走三堆石头，分数变为6。现在Bimal的分数是7，Bimal获胜。
为了解决这个问题，我们将遵循以下步骤：
为了解决这个问题，我们将遵循以下步骤：
定义一个大小为n + 10的数组dp
定义一个大小为n + 10的数组sum
对于初始化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），执行：
对于初始化k := i + 1，当k <= i + 3 且 k <= n时，更新（k增加1），执行：
dp[i] := dp[i] 和 sum[i] - dp[k] 的最大值
total := sum[0]
x := dp[0]
y := total - 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
浏览量：165
