洛谷P1860——新魔法药水

女爷i 2021-10-18 11:58 197阅读 0赞

传送门：[QAQQAQ][]

题意：商店里有N种药水，每种药水都有一个售价和回收价。小S攒了V元钱，还会M种魔法，可以把一些药水合成另一种药水。他一天可以使用K次魔法，问他一天最多赚多少钱？

N<=60 M<=240

V<=1000

k<=30

思路：这是一道比较有技术含量的DP题。

我们定义$dp\[i\]\[j\]$为消耗了$i$个金币（金币不能回收），使用了$j$次魔法能得到的最多钱（最后求答案时注意要$dp\[i\]\[j\]-i$）

在直接转移的过程中，我们无法知道使用的金币都花在了哪些药品上，各种魔法又都用了几次，直接枚举又不知如何下手，所以我们要定义辅助数组：

我们定义$cost\[i\]\[j\]$为最终消耗了$j$次魔法，得到了药品$i$的最小花费，这样转移方程就很容易了：  
**$dp\[i\]\[j\]=max(dp\[i-cost\[p\]\[t\]\]\[j-t\]+w\[p\])$**

$cost\[i\]\[j\]=min(\\sum cost\[magic\[p\].to\[t\]\]\[r\]) (\\sum r=j-1)$

而在处理$cost\[i\]\[j\]$时我们又遇到了一些难题：我们没法知道在得到$i$的魔法中每种原料到底用了几次，其“下层”的魔法各用了几次，所以我们要再开一个辅助数组

我们定义对于当前搜到的魔法$i$，$ant\[t\]\[r\]$为前该魔法前$t$个物品使用了$r$次魔法的最小花费

我们可以通过$t$逐步增大来更新后面的$ant$，其中$cost$和$ant$数组是互相利用的。

（在代码实现方面，要注意$init$函数里的循环顺序，一定要先枚举使用魔法数，这样才能保证在当前枚举到魔法数$j$时前面所有比$j$小的$ant$,$cost$数组已经最优化，这样就可以无忧无虑地转移啦~~）

代码：（用刷表写的，之前刷表越界了。。。）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int inf=(int)1e9;
    
    int cost[300][300],dp[1020][300],ant[301][50];
    int n,m,v,k;
    int b[10001],s[10001];
    struct node{
        int from,len;
        int to[101];
    }E[250];
    
    void checkmax(int &x,int y)
    {
        if(x<y) x=y;
    }
    
    void checkmin(int &x,int y)
    {
        if(x>y) x=y;
    }
    
    void init()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=k;j++) cost[i][j]=b[i];
        }
        for(int j=1;j<=k;j++)
        {
            for(int i=1;i<=m;i++)
            {
                for(int t=1;t<=E[i].len;t++)
                {
                    for(int r=0;r<=j-1;r++)
                    {
                        ant[t][r]=inf;
                        for(int p=0;p<=r;p++) checkmin(ant[t][r],ant[t-1][p]+cost[E[i].to[t]][r-p]);
                    }
                }
                checkmin(cost[E[i].from][j],ant[E[i].len][j-1]);
            }
        }
    }
    
    void solve()
    {
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=v;i++)
        {
            for(int j=0;j<=k;j++)
            {
                for(int t=1;t<=n;t++)//新加药水种类 
                {
                    for(int p=0;p<=k-j;p++)//新用魔法次数 
                    {
                        if(i+cost[t][p]>v||j+p>k) continue;
                        checkmax(dp[i+cost[t][p]][j+p],dp[i][j]+s[t]);
                    }
                }
            }
        }
        int ans=0;
        for(int i=0;i<=v;i++)
        {
            for(int j=0;j<=k;j++) checkmax(ans,dp[i][j]-i);
        }
        cout<<ans<<endl;
    }
    
    int main()
    {
        scanf("%d%d%d%d",&n,&m,&v,&k);
        for(int i=1;i<=n;i++) scanf("%d%d",&b[i],&s[i]);
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&E[i].from);
            scanf("%d",&E[i].len);
            for(int j=1;j<=E[i].len;j++) scanf("%d",&E[i].to[j]);
        }
        init();
        solve();
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11306264.html

[QAQQAQ]: https://www.luogu.org/problem/P1860
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211018/01f76082798a46efa6a3e70909db4e27.png