資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中預測獲勝者
假設我們有一個分數陣列，這些分數是非負整數。第一個玩家從陣列的兩端選擇一個數字，然後是第二個玩家，然後是第一個玩家，依此類推。每次玩家選擇一個數字後，該數字將不再供其他玩家使用。這種情況持續到所有分數都被選擇。獲得最高分數的玩家獲勝。因此，如果我們有分數陣列，我們必須預測玩家 1 是否獲勝。
因此，如果輸入類似於 [1, 5, 233, 7]，則輸出將為 True，因為第一個玩家選擇了 1。然後第二個玩家必須在 5 和 7 之間選擇。無論第二個玩家選擇哪個數字，第一個玩家都可以選擇 233。最後，第一個玩家的分數（234）高於第二個玩家的分數（12），因此我們需要返回 true，因為第一個玩家可以獲勝。
為了解決這個問題，我們將遵循以下步驟：
如果 n 等於 1，則：
返回 true
定義一個大小為 n x n 的陣列 player1，一個大小為 n x n 的陣列 player2，以及一個大小為 n x n 的陣列 sum。
初始化 i := 0，當 i < n 時，更新（i 增加 1），執行：
初始化 j := 0，當 j < n 時，更新（j 增加 1），執行：
player1[i, j] := -1
player2[i, j] := -1
初始化 i := 0，當 i < n 時，更新（i 增加 1），執行：
初始化 j := i，當 j < n 時，更新（j 增加 1），執行：
如果 i 等於 j，則：
sum[i, j] := arr[i]
否則
sum[i, j] := arr[j] + sum[i, j - 1]
初始化 length := 1，當 length <= n 時，更新（length 增加 1），執行：
初始化 i := 0，當 i + length - 1 < n 時，更新（i 增加 1），執行：
end := i + length - 1
如果 i + 1 <= end，則：
player1[i, end] := arr[i] + ((如果 player2[i + 1, end] 等於 - 1，則 0，否則 player2[i + 1, end])) 和 arr[end] + ((如果 player2[i, end - 1] 等於 -1，則 ，否則 player2[i, end - 1])) 的最大值
否則
player1[i, end] := arr[i]
player2[i, end] := sum[i, end] - player1[i, end]
當 player1[0, n - 1] >= player2[0, n - 1] 時返回 true，否則返回 false
示例
讓我們檢視以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
lli solve(vector <int> arr, lli n){
if (n == 1)
return true;
lli player1[n][n], player2[n][n], sum[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
player1[i][j] = -1;
player2[i][j] = -1;
}
}
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (i == j) {
sum[i][j] = arr[i];
}
else {
sum[i][j] = arr[j] + sum[i][j - 1];
}
}
}
for (int length = 1; length <= n; length++) {
for (int i = 0; i + length - 1 < n; i++) {
lli end = i + length - 1;
if (i + 1 <= end)
player1[i][end] = max(arr[i] + (player2[i + 1][end] == -1 ? 0 : player2[i + 1][end]), arr[end] + (player2[i][end - 1] == -1 ?: player2[i][end - 1]));
else
player1[i][end] = arr[i];
player2[i][end] = sum[i][end] - player1[i][end];
}
}
return player1[0][n - 1] >= player2[0][n - 1];
}
bool PredictTheWinner(vector<int>& nums) {
return solve(nums, nums.size()) ;
}
};
main(){
Solution ob;
vector<int> v = {1, 5, 233, 7};
cout << (ob.PredictTheWinner(v));
}輸入
{1, 5, 233, 7}輸出
1
239 次檢視
