2

来玩个游戏：

一排有 n 叠硬币。第 i 个堆栈由 d_i 个硬币组成。两名玩家：Player1、Player2 交替移动。轮到他的玩家只能拿第一个堆栈或最后一个堆栈或两者。当没有硬币时，游戏结束。每个玩家都希望在最后拥有尽可能多的硬币。播放器 1 开始。

我想知道算法（听起来像贪心算法）来计算每个玩家在游戏结束时有多少硬币，而两者都处于最佳状态。

我不知道如何处理这样的算法。只是猜测策略还是有一些方法可以推断出来？或者，实现算法可能是一个太奇怪的问题？

示例（从第一个到第 n 个堆叠的硬币）：

1, 100, 1 - 玩家分别有 2 和 100 个硬币（不幸的是，第一个玩家只能拿第一个和最后一个筹码 - 第二个玩家总是拿 100 个硬币的筹码）

1, 1, 100, 1, 1, 5 - 玩家分别有 8 和 101 个硬币（我认为这是在最佳游戏之后 - 首先取 5 和 1，然后取 1 以防止玩家 1 拿 100 个硬币堆叠。如果玩家 1第一步拿不到 6 个硬币，他总是少于 8 个硬币）。

我希望我足够详细地说明问题。你同意这很有趣吗？:) 有人可以帮忙吗？

4

2 回答 2

1

添加到 @Peter 的动态编程解决方案：

我认为重复性看起来有点像以下：考虑到 Let

的硬币堆栈，表示 Player1 可能获得的最高分数。然后，A[i,..j]
dp[i, j]

dp[i, j] = MAX {
                MIN( dp[i+2, j], dp[i+1, j-1], dp[i+2, j-1]) + A[i], //Case when Player2 will try to make the most of it if Player1 picks ith coin.
                MIN( dp[i+1, j-1], dp[i, j-2], dp[i+1, j-2]) + A[j], //Case when Player2 will try to make the most of it if Player1 picks the jth coin.
                MIN( dp[i+2, j-1], dp[i+1, j-2], dp[i+2, j-2]) + A[i] + A[j] // Case when Player2 will try to make the most of it when Player1 picks both the ith and jth coins.
               }

因为只有 N^2 种可能的游戏状态。它可以通过填充大小为 N^2 的 dp 表来实现。

对于 C++ 爱好者：

#include<iostream>
using namespace std;
int Solve(int A[], int N, int **dp, int i, int j){
        if(dp[i][j] != -1)
                return dp[i][j];
        if(j<i)
                return 0;
        else if(j==i)
                return A[i];
        else if( (j-i) == 1)
                return (A[i] + A[j]);
        else{
                int opt1 = min(Solve(A, N, dp, i+2, j), Solve(A, N, dp, i+1, j-1));
                opt1 = min(opt1, Solve(A, N, dp, i+2, j-1));
                int opt2 = min(Solve(A, N, dp, i+1, j-1), Solve(A, N, dp, i, j-2));
                opt2 = min(opt2, Solve(A, N, dp, i+1, j-2));
                int opt3 = min(Solve(A, N, dp, i+2, j-1), Solve(A, N, dp, i+1, j-2));
                opt3 = min(opt3, Solve(A, N, dp, i+2, j-2));
                int res = max(opt1+A[i], opt2+A[j]);
                res = max(res, opt3+A[i]+A[j]);
                dp[i][j] = res;
                return res;

        }
}
int main(){
        int N;
        int A[N];
        cin >> N;
        for(int i=0; i<N; ++i)
                cin >> A[i];
        int **dp;
        dp = new int* [N];
        for(int i=0; i<N; ++i)
                dp[i] = new int[N];
        for(int i=0; i<N; ++i)
                for(int j=0; j<N; ++j)
                        dp[i][j] = -1;
        Solve(A, N, dp, 0, N-1);
        cout << dp[0][N-1] << endl;
        for(int i=0; i<N; ++i)
                delete [] dp[i];
        delete []dp;
        return 0;
}

此外，正如@Peter指出的那样，您对第二个示例的分析是错误的。Player1 实际上有一个策略可以通过获得 102 个硬币来赢得该游戏。

于 2012-11-26T22:20:27.330 回答
0

如果仅存在 a 到 b-1 范围内的堆栈，您可以通过 O(n^2) 中的动态编程解决此问题，即解决最佳策略的子问题。

Python代码：

A=[1, 1, 100, 1, 1, 5]
#A=[1, 100, 1]

cache={}
def go(a,b):
    """Find greatest difference between player 1 coins and player 2 coins when choosing from A[a:b]"""
    if a==b: return 0 # no stacks left
    if a==b-1: return A[a] # only one stack left
    key=a,b
    if key in cache:
        return cache[key]

    v=A[a]-go(a+1,b) # taking first stack
    v=max(v,A[b-1]-go(a,b-1)) # taking last stack
    v=max(v,A[a]+A[b-1]-go(a+1,b-1)) # taking both stacks

    cache[key]=v
    return v

v = go(0,len(A))
n=sum(A)
print (n+v)/2,(n-v)/2

这就是说，第二种情况的最佳游戏实际上是第一个人只取最左边的 1。从那时起，他可以保证他会抓住 100，所以他赢了。

（玩家1胜102，玩家2胜7）

有 O(n^2) 个子博弈，所以这个算法需要时间 O(n^2)

子游戏（和最佳的第一玩家/第二玩家硬币）是：

 [1, 5] 6 0
 [1, 1] 2 0
 [1, 100] 101 0
 [100, 1] 101 0
 [1, 1] 2 0
 [1, 100, 1] 2 100
 [1, 1, 5] 6 1
 [100, 1, 1] 101 1
 [1, 1, 100] 101 1
 [100, 1, 1, 5] 105 2
 [1, 100, 1, 1] 101 2
 [1, 1, 100, 1] 101 2
 [1, 100, 1, 1, 5] 7 101
 [1, 1, 100, 1, 1] 102 2
 [1, 1, 100, 1, 1, 5] 102 7

因此，例如，假设我们已经为较小的游戏找到了所有最佳玩法，并希望为 [1,1,100,1,1,5] 找到最佳玩法。

我们所做的只是依次考虑每一步：

  1. 拿第一个筹码，这将使我们赢得 1，然后离开游戏 [1,100,1,1,5]，我们从子问题中知道，我们将赢得 101，总共 102。
  2. 拿最后一个筹码，这将使我们赢得 5，然后离开游戏 [1,1,100,1,1] 只会为我们赢得额外的 2，总共 7。
  3. 拿两个筹码，这将使我们赢 6，然后离开游戏 [1,100,1,1] 如果玩家 2 发挥最佳，我们只会再赢 2，总共 8

所以最好的做法是只拿第一堆。

于 2012-11-26T20:04:40.883 回答