题解 P2760 【科技庄园】

· · 题解

分析题目

要素无非就以下几个：

再转变一下

不难看出，这就是多重背包

注意点：

背包总体积的处理

乍一看，题目有两个“体积”，一个时间，一个体力。但实际并非如此。

因为我们每走一步，时间和体力都减一，只要时间到 0 或者 体力到 1 就不能再走了，所以背包体积就可以取 总时间 和 总体力-1 的较小值 。

另外，为什么总体力要减一？

由于PFT不是机器人，所以他的体力并不是无限的，他不想摘很多的桃以至体力为0，而白白把桃给Life。

体力不能到0的哦~

物品消耗的处理

每个物品的消耗就是(0,0)到当前坐标的距离，但需要注意的是这里的距离不是欧几里得距离！！

因为PFT只能上下左右移动，不能斜着跑。

所以每个物品的消耗：

设当前坐标为(x,y)，则消耗为2*(x+y)

为什么乘2？因为是往返啊……

代码

这里使用了二进制优化

#include<iostream>
#include<cstdio>
using namespace std;
struct Object
{
    long long cost,value,number;
    //每个物品的消耗，价值和次数
    //每个桃数的距离，桃子数量，和采摘次数
}a[10005];
long long dp[10005];
int n,h,l,Time,Tili,Bag;
//总物品数，行，列，总时间，总体力，背包体积
void ZeroOnePack(int cost,int value)
{
    for(int i=Bag;i>=cost;i--)
    {
        dp[i]=max(dp[i],dp[i-cost]+value);
    }
}
//01背包板子
void CompletePack(int cost,int value)
{
    for(int i=cost;i<=Bag;i++)
    {
        dp[i]=max(dp[i],dp[i-cost]+value);
    }
}
//完全背包板子
void MultiPack(int cost,int value,int amount)
{
    if(Bag<=cost*amount)
    {
        //背包体积小于等于物品的总体积
        //那么随便拿，完全背包
        //Trace On!
        CompletePack(cost,value);
        return;
    }
    for(int k=1;k<amount;k<<=1)
    {
        ZeroOnePack(cost*k,value*k);
        amount-=k;
    }
    ZeroOnePack(cost*amount,value*amount);
    //二进制优化的过程↑
}
//上面是二进制优化的多重背包板子
//如果有不会二进制优化的同学，可以把我这个板子粘下来背
//我感觉这个板子相比别的大佬写的板子还是很简单好记的
int main()
{
    scanf("%d%d%d%d",&h,&l,&Time,&Tili);
    n=h*l;
    //获得总物品数
    int cnt=0;
    //记录物品下标
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=l;j++)
        {
            scanf("%lld",&a[++cnt].value);
            //输入当前桃子数量，即物品价值
            a[cnt].cost=i+j<<1;
            //同时处理出当前桃数的距离
            //位运算，等价于(i+j)*2
        }
    }
    cnt=0;
    //重新输入，清零下标
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=l;j++)
        {
            scanf("%lld",&a[++cnt].number);
            //输入可采摘次数
        }
    }
    Bag=min(Time,Tili-1);
    //计算背包体积
    for(int i=1;i<=n;i++)
    {
        MultiPack(a[i].cost,a[i].value,a[i].number);
    }
    printf("%lld\n",dp[Bag]);
    return 0;
}

附赠多重背包二进制优化的板子

void ZeroOnePack(int cost,int value)
{
    for(int i=Bag;i>=cost;i--)
    {
        dp[i]=max(dp[i],dp[i-cost]+value);
    }
}
void CompletePack(int cost,int value)
{
    for(int i=cost;i<=Bag;i++)
    {
        dp[i]=max(dp[i],dp[i-cost]+value);
    }
}
void MultiPack(int cost,int value,int amount)
{
    if(Bag<=cost*amount)
    {
        CompletePack(cost,value);
        return;
    }
    for(int k=1;k<amount;k<<=1)
    {
        ZeroOnePack(cost*k,value*k);
        amount-=k;
    }
    ZeroOnePack(cost*amount,value*amount);
}
signed main()
{
    ......
    //省略输入……
    for(int i=1;i<=n;i++)
    {
        MultiPack(a[i].cost,a[i].value,a[i].number);
    }
    printf("%lld\n",dp[Bag]);
}

都看完了，不点个赞再走吗（滑稽