3

我在算法游戏上练习这个问题，我尝试了以下问题，但找不到有效的方法::

所以你能帮帮我吗。这是问题所在。

这是确切的链接： http: //community.topcoder.com/tc?module =Static&d1=match_editorials&d2=srm228

4

4 回答 4

2

您可以使用动态规划来解决它。状态可以表示为：

set of available coins,
whos turn it is

对于每个州，您应该计算该人反过来可以赢得的最大金额。

提示：这个游戏的规则允许描述set of available coins为间隔。

@编辑

for(int interval_size = 1; interval_size <= n; interval_size++) {
    for(int interval_start = 0; interval_start + interval_size <= n; interval_start++) {
         // result[interval_start][interval_start + interval_size] depends only on
         // -> result[interval_start][interval_start + interval_size - 1]
         // -> result[interval_start + 1][interval_start + interval_size]
    }
}
于 2012-04-05T09:24:07.200 回答
2

让dp[i, j] = maximum profit alice can make for the coints i, ... j.

我们有：

dp[i, i] = input[i] for all 1 <= i <= N
dp[i, i + 1] = max(input[i], input[i + 1])
dp[i, j] = max(// take first coin, opponent will minimize your next move
               input[i] + min(dp[i + 2, j], dp[i + 1, j - 1]),
               // take last coin, opponent will still minimize your next move
               input[j] + min(dp[i, j - 2], dp[i - 1, j - 1]))
于 2012-04-05T09:33:26.507 回答
1

我假设你想自己解决这个问题，所以我给你一个提示：这个问题有最优子结构。

想象一下，你有两种N-1硬币的解决方案（没有最左边的一个，也没有最右边的一个）。N那么计算硬币的解决方案会很容易吗？

您可以使用两种相关的技术来利用此属性 -动态编程及其称为memoization的子类型。这个想法是为每个子问题存储一个解决方案，L其中左侧R缺少硬币，右侧缺少硬币（使用NxN数组）。在解决子问题之前，请检查数组以查看您是否已经解决了它。您最多需要解决大多数N^2/2子问题才能得出解决方案。

这是一个记忆解决方案的伪代码：

// solved[L][R] array contains the highest value a player could get
// on a subproblem where L coins are missing from the left
// and R are missing from the right of the original sequence on his move
int solved[N][N] // initialize each element to -1.
int coins[N]     // initialize with coin values 

int solve(int L, int R) {
    if (L+R == N) return 0; // No coins remain
    if (solved[L][R] >= 0) return solved[L][R];
    int remaining = sum(coins from L to R)
    int takeLeft = remaining - solve(L+1, R);
    int takeRight = remaining - solve(L, R+1);
    int result = max(takeLeft, takeRight);
    solved[L][R] = result;
    return result;
}

main() {
    int alice = solve(0, 0);
    int bob = sum(coins) - alice;
}

我记得 TopCoder 在 2005 年初或 2006 年的某个时候运行过这个问题，但我不记得足够的细节来搜索他们的问题档案。

于 2012-04-05T09:33:10.253 回答
1 
//@ IVlad ::Implement your code ,its giving incorrect answer.Had I implemented it properly??
int coins[1000];
int dp[1000][1000];
int main()
 {
int T,N;//N=How many coins are there
cin>>T; //No of Test Cases.
while(T--)
{
    cin>>N;
    for(int i=1;i<=N;++i)
    {
        cin>>coins[i];
    }
    for(int i=1;i<=N;++i)
    {
        dp[i][i]=coins[i];
    }
    for(int i=1;i<=N;++i)
    {
        if(i+1<=N)
        dp[i][i + 1] = max(coins[i], coins[i + 1]);
    }
    for(int i=1;i<=N;++i)
    {
        for(int j=1;j<=N;++j)
        {
            if((i+2)<=N && (i+1)<=N && (j-2)>=1 && (i-1)>=1 && (j-1)>=1)
            dp[i][j]=max( (coins[i] + min(dp[i + 2] [j], dp[i + 1][ j - 1])),coins[j] + min(dp[i] [j - 2], dp[i - 1] [j - 1]));
        }
    }
    cout<<dp[1][N]<<endl;//Answer
}

return 0;

}

于 2012-04-05T20:14:33.473 回答