題目描述

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

輸入輸出樣例

5 1 3 1 7 2 輸出樣例#1：
9 
說明
There are five coins with the values 1, 3, 1, 7, and 2.
The first player starts by taking a single coin (value 1). The opponent takes one coin as well (value 3). The first player takes two more coins (values 1 and 7 -- total 9). The second player gets the leftover coin (value 2-- total 5).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
DP+博弈論~
和上一道差不多的做法，只是要多限制一下取數，而且只能從一邊取~
用f[i][j]表示該取i，上一次取了j個的最大得分，則因為所有塊的權值都>0，所以只要用2*j和2*j-1來更新答案就可以了，具體DP方程見代碼~
#include<cstdio>#include<cstring>#include<iostream>using namespace std;int n,a[2002],f[2001][2001],ans;int read(){	int totnum=0,f=1;char ch=getchar();	while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}	while(ch>='0' && ch<='9') {totnum=(totnum<<1)+(totnum<<3)+ch-'0';ch=getchar();}	return totnum*f;}int main(){	n=read();	for(int i=n;i;i--) a[i]=read();	for(int i=2;i<=n;i++) a[i]+=a[i-1],f[i][i]=a[i];	for(int i=1;i<=n;i++)	  for(int j=1;j<=n;j++)	  {	  	f[i][j]=f[i][j-1];	  	if(i>=2*j) f[i][j]=max(f[i][j],a[i]-f[i-2*j][2*j]);	  	if(i+1>=2*j) f[i][j]=max(f[i][j],a[i]-f[i-2*j+1][2*j-1]);	  }	printf("%d/n",f[n][1]);	return 0;}