洛谷3004 [USACO10DEC]Treasure Chest

题解 动态规划 动态规划-区间DP 提高+/省选-
题目链接 编辑文章

双倍经验:洛谷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]);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空