问题描述
让我们玩一个游戏：
有硬币的行n堆栈。第i个堆栈由d_i硬币。两名球员：PLAYER1，Player2出招交替进行。玩家在轮到他只能拿一个堆栈或最后一个堆栈或两者。当没有硬币离开了游戏结束。每个玩家都想拥有尽可能多的硬币可能在年底。 PLAYER1启动。
There are n stacks of coins in a row. i-th stack consists of d_i coins. Two players: Player1, Player2 make moves alternately. Player in his turn can only take first stack or last stack or both of them. The game ends when there are no coins left. Each player wants to have as many coins as possible at the end. Player1 starts.
我想知道算法（听起来像贪心算法）来计算每个玩家有多少金币了，在比赛结束的时候双方扮演着最佳的。
I was wondering about algorithm (sounds like greedy algorithm) to count how many coins each player has at the end of the game when both plays optimal.
我没有任何想法如何处理这样的算法。只是猜测策略或有某种方式来演绎呢？或者，也许这未免奇怪的问题，以实现一个算法？
I don't have any idea how to approach such algorithms. Just guess strategy or there is some way to deduce it? Or maybe it's rather too weird problem to implement an algorithm?
实例（硬币堆，从第一个到第n个）：
Examples (coins in stacks from first to n-th):
1，100，1 - 玩家有2个和100分别币（遗憾的是第一个玩家只能取一个和最后一个堆栈 - 第二位玩家将始终以堆叠100金币）
1, 100, 1 - players have 2 and 100 coins respectively (unfortunately first player can only take first and last stack - second player will always take stack with 100 coins)
1，1，100，1，1，5 - 球员分别为8和101金币（我认为这是最佳的比赛结束后 - 先取5和1，那么第二个需要1至prevent PLAYER1采取栈有100个硬币。如果PLAYER1需要不到6个硬币在他的第一个动作，他将永远少于8硬币）。
1, 1, 100, 1, 1, 5 - players have 8 and 101 coins respectively (I think this is after optimal game - first take 5 and 1, then second take 1 to prevent player1 from taking stack with 100 coins. If player1 take less than 6 coins in his first move, he will always have less than 8 coins).
我希望指定我足够的问题。你是否同意，这是有趣的？ :)任何人可以帮助？
I hope I specified enough the problem. Do you agree that it is interesting? :) Can anybody help?
推荐答案
添加到 @彼得的动态规划的解决方案：
我认为，复发看起来有点像以下：
考虑到硬币堆从 A [我，.. J]
让 DP [I，J] 重presents的最高分是PLAYER1都不可能得到的。然后，
Adding to @Peter's dynamic programming solution:
I think the recurrence would look somewhat like following:
Considering the coin stacks ranging from A[i,..j]
Let, dp[i, j] represents the max score that Player1 can possibly get. Then,
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可能游戏状态。它可以通过填充大小的DP表来实现N ^ 2。
As there are only N^2 possible game states. It can be implemented by filling up a dp table of size N^2.
有关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金币赢得那场比赛。
Also, as @Peter pointed out your analysis for 2nd example is wrong. Player1 actually has a strategy to win that game by scoring 102 coins.
这篇关于算法游戏币的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！