洛谷3004 [USACO10DEC]Treasure Chest

双倍经验：洛谷2734 游戏 A Game （还不用滚动数组）

题意

有 $N$ 个数，两个人轮流取，每次可以取左右两端的数。两个人都绝顶聪明，问第一个人最多能取到多少。

$N\le 5000$ 。空间限制 $64M$ 。

题解

用 $f[i][j]$ 表示在 $[i,j]$ 最多能取到多少，用 $sum[i][j]$ 表示 $[i,j]$ 的和。因为两个人都会取最优方案，所以方程式为：

$$f[i][j]=s[i][j]-\min (f[i+1][[j],f[i][j+1])$$

但这样开数组空间就不够了，考虑滚动数组。

用 $f[i]$ 表示以 $i$ 开始，长度为 $k$ （即DP时枚举的）的最优解。方程式就可以变成：

$$f[i][j]=s[i][j]-\min (f[i],f[i+1])$$

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,s[5005],f[5005];

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) f[i]=read(),s[i]=s[i-1]+f[i];
    for (int k=2;k<=n;k++)
    {
        for (int i=1;i+k-1<=n;i++)
        {
            int j=i+k-1;
            f[i]=s[j]-s[i-1]-min(f[i],f[i+1]);
        }
    }
    return !printf("%d",f[1]);
}