最大选择数组的第一个或最后一个元素

Question

你能帮我解决这个问题吗::((

给定一个数组 A[] 有 n 个正数 (n<=5000)。彼得和艾玛玩一个选择数字的游戏。当轮到每个人时，他们可以选择数组的第一个或最后一个元素，然后增加 his/her 分数并将该元素从数组中删除。彼得先上场。

你必须找到谁能赢以及他们的分数，彼得和艾玛都是最好的球员

示例：

A = {4,5,1,3}

第一轮，彼得可以选择第一个数字（4）或最后一个数字（3），所以他选择3然后将其删除。

// A={4,5,1}

在第二轮，Emma 可以选择第一个数字 (4) 或最后一个数字 (1)，所以她选择 4 然后将其删除。

// A={5,1}

第三轮，彼得可以选择第一个数字（5）或最后一个数字（1），所以他选择5然后将其删除。

// A={1}

最后一回合，Emma只选了1个号码（1），然后去掉1

现在数组为空所以游戏结束，Peter有3+5=8的分数；艾玛有4+1=5分。所以彼得赢了。

解释为什么彼得没有9分（4+5）而艾玛没有4分（1+3）。因为他们都是最好的玩家，所以当彼得去掉数字 3 时，艾玛会选择 4 而不是 1\

我用过回溯但时间有限

Answer 1

基本思路如下：

让我们称 score(first, right) 一个玩家在剩余元素从 first 到 last 元素中可以获得的最好分数。

然后，如果玩家A select first元素，那么玩家B将获得score(first+1, last)，并且然后玩家 A 将获得 sum - player B score.

如果玩家 A select 最后一个元素，则使用相同的逻辑：玩家 B 将获得 score(first, last-1)

这可以很容易地以递归方式实现。

必须实现记忆化以避免重复相同的计算。

复杂度：O(N^2)。

#include <iostream>
#include <vector>
#include <numeric>
#include <tuple>

int sum;
int sum_left;
std::vector<std::vector<int>> mem;

int score_rec (const std::vector<int> &A, int first, int last) {
    if (mem[first][last] >= 0) return mem[first][last];

    sum_left -= A[first];
    int score1 = A[first] + sum_left - score_rec (A, first + 1, last);
    sum_left += A[first];
    
    sum_left -= A[last];
    int score2 = A[last] + sum_left - score_rec (A, first, last - 1);
    sum_left += A[last];
    
    int score = std::max (score1, score2);
    mem[first][last] = score;
    
    return score;
}

std::tuple<int, int> scores (const std::vector<int> &A) {
    int n = A.size();
    sum = std::accumulate (A.begin(), A.end(), 0);
    sum_left = sum;
    for (int i = 0; i < n; ++i) {
        mem.emplace_back (std::vector<int> (n, -1));
    }
    for (int i = 0; i < n; ++i) mem[i][i] = A[i];

    int scoreA = score_rec (A, 0, n-1);
    int scoreB = sum - scoreA;
    
    return {scoreA, scoreB};
}

int main () {
    std::vector<int> A = {4, 5, 1, 3};
    auto[scoreA, scoreB] = scores (A);
    std::cout << scoreA << " " << scoreB << std::endl;
    return 0;
}

最大选择数组的第一个或最后一个元素

Max chosen of first or last elements of array

arrays

algorithm

dynamic-programming