bzoj2101【Usaco2010 Dec】Treasure Chest 藏寶箱

Description

Bessie and Bonnie have found a treasure chest full of marvelous gold coins! Being cows, though, they can't just walk into a store and buy stuff, so instead they decide to have some fun with the coins. The N (1 <= N <= 5,000) coins, each with some value C_i (1 <= C_i <= 5,000) are placed in a straight line. Bessie and Bonnie take turns, and for each cow's turn, she takes exactly one coin off of either the left end or the right end of the line. The game ends when there are no coins left. Bessie and Bonnie are each trying to get as much wealth as possible for themselves. Bessie goes first. Help her figure out the maximum value she can win, assuming that both cows play optimally. Consider a game in which four coins are lined up with these values: 30 25 10 35 Consider this game sequence: Bessie Bonnie New Coin Player Side CoinValue Total Total Line Bessie Right 35 35 0 30 25 10 Bonnie Left 30 35 30 25 10 Bessie Left 25 60 30 10 Bonnie Right 10 60 40 -- This is the best game Bessie can play.

貝西和邦妮找到了一個藏寶箱，裡面都是金幣！但是身為兩頭牛，她們不能到商店裡把金幣換成好吃的東西，於是她們只能用這些金幣來玩游戲了。 藏寶箱裡一共有N枚金幣，第i枚金幣的價值是Ci。貝西和邦妮把金幣排成一條直線，她們輪流取金幣，看誰取到的錢最多。貝西先取，每次只能取一枚金幣，而且只能選擇取直線兩頭的金幣，不能取走中間的金幣。當所有金幣取完之後，游戲就結束了。 貝西和邦妮都是非常聰明的，她們會采用最好的辦法讓自己取到的金幣最多。請幫助貝西計算一下，她能拿到多少錢？

Input

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

第一行：單個整數N，表示硬幣的數量，1<=N≤5000 第二行到第N+1行：第i+l行有一個整數Ci，代表第i塊硬幣的價值，1≤Ci≤5000

Output

* Line 1: A single integer, which is the greatest total value Bessie can win if both cows play optimally.

第一行：單個整數，表示如果雙方都按最優策略玩游戲，先手可以拿到的最大價值

Sample Input

4
30
25
10
35

Sample Output

60

HINT

(貝西最好的取法是先取35，然後邦妮會取30，貝西再取25，邦妮最後取10)

Source

Silver

動態規劃的空間優化，感覺方法還是不錯的。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 5005
using namespace std;
int n,x;
int f[maxn],sum[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();
	sum[0]=0;
	F(i,1,n)
	{
		x=read();
		sum[i]=sum[i-1]+x;
		f[i]=x;
	}
	F(j,1,n-1) F(i,1,n-j) f[i]=sum[i+j]-sum[i-1]-min(f[i],f[i+1]);
	printf("%d\n",f[1]);
}
</algorithm></cmath></cstring></cstdlib></cstdio></iostream>