洛谷2964 A Coin Game

题目描述

Farmer John’s cows like to play coin games so FJ has invented with a
new two-player coin game called Xoinc for them.

Initially a stack of N (5 <= N <= 2,000) coins sits on the ground;
coin i from the top has integer value C_i (1 <= C_i <= 100,000).

The first player starts the game by taking the top one or two coins
(C_1 and maybe C_2) from the stack. If the first player takes just the
top coin, the second player may take the following one or two coins in
the next turn. If the first player takes two coins then the second
player may take the top one, two, three or four coins from the stack.
In each turn, the current player must take at least one coin and at
most two times the amount of coins last taken by the opposing player.
The game is over when there are no more coins to take.

Afterwards, they can use the value of the coins they have taken from
the stack to buy treats from FJ, so naturally, their purpose in the
game is to maximize the total value of the coins they take. Assuming
the second player plays optimally to maximize his own winnings, what
is the highest total value that the first player can have when the
game is over?

MEMORY LIMIT: 20 MB

农夫约翰的奶牛喜欢玩硬币游戏.

初始时，一个有N枚硬币的堆栈放在地上，从堆顶数起的第i枚硬币的币值 为Ci

开始玩游戏时，第一个玩家可以从堆顶拿走一枚或两枚硬币.如果第一个玩家只拿走堆顶的
一枚硬币，那么第二个玩家可以拿走随后的一枚或两枚硬币.如果第一个玩家拿走两枚硬币，则第二个玩家可以拿走1，2，3，或4枚硬币.在每一轮中，当前的玩家至少拿走一枚硬币，至多拿
走对手上一次所拿硬币数量的两倍.当没有硬币可拿时，游戏结束.

两个玩家都希望拿到最多钱数的硬币.请问，当游戏结束时，第一个玩家最多能拿多少钱 呢？ 输入输出格式 输入格式：

Line 1: A single integer: N
Lines 2..N+1: Line i+1 contains a single integer: C_i

输出格式：

Line 1: A single integer representing the maximum value that can be made by the first player.

用$dp[i][j]$表示该取第$i$个硬币，上一个人取了$j$个的最大收益。如果直接枚举这一次取多少个转移是$O(n^3)$的，但是可以发现$dp[i][j]$比$dp[i][j-1]$多的就是这一次取$2*j-1$和$2*j$两种情况，其他情况可以直接继承过来。这样转移的复杂度变成了常数，总复杂度$O(n^2)$。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int oo=0x3f3f3f3f;
int dp[2010][2010],c[2010],s[2010],n;
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&c[i]),s[i]=s[i-1]+c[i];for (int i=n;i;i--)for (int j=1;j<=i;j++)dp[i][j]=max(dp[i][j-1],max(i+2*j-1<=n+1?s[n]-s[i-1]-dp[i+2*j-1][2*j-1]:-oo,i+2*j<=n+1?s[n]-s[i-1]-dp[i+2*j][2*j]:-oo));printf("%d\n",dp[1][1]);
}