题目描述
贝西和伯尼找到了一个装满了金币的宝箱！但是，作为奶牛，他们不能随便进入一家商店去买东西。所以他们决定去用这些金币玩一个游戏。
这里有N（1<=N<=5000）个硬币，每个都有一个价值C_i（1<=C_i<=5000）。这些硬币被摆成了一行。贝西和伯尼每人一回合。到了一只奶牛的回合时，他就要拿走最左边或者最右边的硬币。当没有硬币时，游戏结束。
贝西和伯尼都想要使自己拿到的金币价值尽量高，贝西先拿。现在贝西想要你帮帮她，算出她最多可以拿多少钱（伯尼也会尽量取到最优）。
输入输出格式
输入格式：
-
Line 1: A single integer: N
- Lines 2..N+1: Line i+1 contains a single integer: C_i
输出格式：
- Line 1: A single integer, which is the greatest total value Bessie can win if both cows play optimally.
代码
其实和2734差不多。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=5005; inline void read(int &x){ x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} } int n; int c[maxn],f[maxn][maxn]; int main(){ read(n); for(int i=1;i<=n;++i) read(c[i]),c[i]+=c[i-1]; for(int i=1;i<=n;++i) f[i][i]=c[i]-c[i-1]; for(int l=2;l<=n;++l) for(int i=1;i+l-1<=n;++i){ int j=i+l-1; f[i][j]=c[j]-f[i+1][j]-c[i-1]; f[i][j]=max(f[i][j],c[j]-c[i-1]-f[i][j-1]); } printf("%d ",f[1][n]); return 0; }