题解 P3004 【[USACO10DEC]宝箱Treasure Chest】

· · 题解

不难写出状态：

令f[l][r]代表区间[l,r]中取钱的最大值，不难写出转移：

f[l][r] = sum[l][r] - min{f[l + 1][r], f[l][r + 1]}

sum[l][r]是区间和

意思就是区间[l, r]由我和对手取，一共取得的是sum个，考虑这次我取的是左边的硬币还是右边的硬币，显然我要让对手得到的最小，用区间的和减去对手的最小值就是我的最大值

观察转移方程我们发现一定是长度大的由长度小的转移过来

不难写出程序：

#include <bits/stdc++.h>
using namespace std;

int N, a[5010], f[5010][5010], sum[5010][5010];

int main()
{
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= N; i++)
        f[i][i] = a[i];
    for (int i = 1; i <= N; i++)
        for (int j = i; j <= N; j++)
            sum[i][j] = sum[i][j - 1] + a[j];
    for (int len = 2; len <= N; len++)
        for (int i = 1; i + len - 1 <= N; i++)
            f[i][i + len - 1] = sum[i][i + len - 1] - min(f[i + 1][i + len - 1], f[i][i + len - 2]);
    printf("%d\n", f[1][N]);
    return 0;
}

交上去qtmd90pts，MLE一个点，把评测鸡吊起来干一顿，然后一看内存，woc64MB想搞鬼？？？

然后我们干脆直接优化掉sum，用前缀和一减

#include <bits/stdc++.h>
using namespace std;

int N, a[5010], f[5010][5010];

int main()
{
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= N; i++)
        f[i][i] = a[i];
    for (int i = 1; i <= N; i++)
        a[i] += a[i - 1];
    for (int len = 2; len <= N; len++)
        for (int i = 1; i + len - 1 <= N; i++)
            f[i][i + len - 1] = a[i + len - 1] - a[i - 1] - min(f[i + 1][i + len - 1], f[i][i + len - 2]);
    printf("%d\n", f[1][N]);
    return 0;
}

交上去qtmd90pts，又tmMLE一个点，把评测鸡吊起来干一顿

然后可以输出数组a的大小，一看100MB(左右)，空间限制是64MB。

然后考虑f数组的使用，我们只用了f数组的一半，所以我们可以开动态内存，避免浪费一般的内存

注意第一维的下标是始终小于第二维的，所以这里偷懒直接把两个下标互换了一下

#include <bits/stdc++.h>
using namespace std;

int N, a[5010], *f[5010];

int main()
{
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= N; i++)
    {
        f[i] = new int[i + 2];
        for (int j = 1; j <= i; j++)
            f[i][j] = 0;
        f[i][i] = a[i];
    }
    for (int i = 1; i <= N; i++)
        a[i] += a[i - 1];
    for (int len = 2; len <= N; len++)
        for (int i = 1; i + len - 1 <= N; i++)
            f[i + len - 1][i] = a[i + len - 1] - a[i - 1] - min(f[i + len - 1][i + 1], f[i + len - 2][i]);
    printf("%d\n", f[N][1]);
    for (int i = 1; i <= N; i++)
    {
        delete []f[i];
        f[i] = 0;
    }
    return 0;
}

关于C++动态内存的使用：

int *p = new int;//申请一个int的空间
int *p = new int[100];//申请100个int的空间，就相当于开大小为100的一维数组
memset(p, 0, sizeof(p));//这样使用是错误的，想一想为什么
delete p;//对应第一行，释放内存
delete []p;//对应第二行的申请数组，释放内存
//如果想申请二维数组可以开一个指针数组(如上面的程序)

备注

当然我们可以通过std的vector(变长数组)，这里我没有实现不知道行不行

题解里有一个一维数组的做法，大家尽量参考那一篇(那才是真正的王道)，我这个就是莫名其妙想出来的卡进空间限制的方法

经验/教训：做题要早一点做否则改了内存就gg了

让我们一起膜拜大佬林瑞堂@olinr