数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
