資料結構
網路
關係資料庫管理系統 (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
