YZOJ P1299 [NOIP福建夏令营]金字塔

发表于 | 更新于 | 阅读次数：

题目描述

小X来到一个雄奇的金字塔挖宝，但是这是一座被诅咒的金字塔，小X必须马上逃离这里，否则小X就会被埋在金字塔里，但他不希望此行落空。

现在小X面前有$N+1$种财宝，每种财宝都有一个价值。第一种财宝重量为0，第二种财宝重量为1，总之第I种财宝重量为$I-1$。现在小X希望拿走$N+M$个物品，但是这$M+N$个物品总重量不能超过N。小X希望能获得最大的价值。你能帮帮他吗？

由于金字塔跟小X一样牛，所以每种财宝无限个。

输入格式

第一行两个正整数$N$，$M$

第二行$N+1$个整数，第$I$个整数代表了第I种财宝的价值

输出格式

一个数，表示最大利润。

样例输入

1
2
5 3
4 7 2 5 -3 6

样例输出

1
47

数据规模与约定

10%满足$N$,$M<=10$

40%满足$N$,$M<=100$

100%满足$N$,$M<=3000$ $abs(财宝价值)<=1000$

这就是一道背包的应用题。你们也可以学习kyz的做法（毕竟他的做法貌似比我的快，空间用的比我小），在这里讲一下我的一种做法。

这是一个比较特殊的动态规划，首先要注意到因为要取到$N+M$个，所以我们可以知道每一次至少要拿走$M+N$件0号物品，所以我们的初始化就是这样。

1
2
for(i=0;i<=n;i++)
    f[i]=(n+m)*a[0];

对于这样的完全背包问题，我们需要找到一个动态规划转移方程。$f[i]$表示$i$的体积下最多得到的价值，$f[j]+a[i]-a[0]$是从j空间转移而来，所以$f[j]+a[i]-a[0]$中$-a[0]$的原因是：我们模拟出来在执行之前，全部都装满了0号物品，所以我们在转移的时候，需要取出一个0号物品，再塞进去一个$i$号物品。

1
f[i+j]=max(f[j]+a[i]-a[0],f[i+j]);

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#define re register
//我没用快读模板是因为有负数，所以我就用了scanf
int n,m;
int a[3001],f[3001]={0};
int main(){
	scanf("%d%d",&n,&m);
	for(re int i=0;i<=n;i++) scanf("%d",&a[i]);
    for(re int i=0;i<=n;i++) f[i]=(n+m)*a[0];    //初始化
    for(re int i=1;i<=n;i++)
        for(re int j=0;j<=n-i;j++)
            f[i+j]=max(f[j]+a[i]-a[0],f[i+j]);    //动态转移方程
    return !printf("%d\n",f[n]);
}

$\color{gray}{\mathfrak{End}}$