Codeforces 106 C Buns【多重背包】

刺骨的言语ヽ痛彻心扉 2022-08-12 13:58 7阅读 0赞

今天拉了一场CF，做了一下，略坑啊、、、首先105A题，竟然卡精度，小数点两位卡精度，需要给他加一个1e-6，算是见识了

题目：[Codeforces 106 C Buns][]

题意：给出一些n克面，以及m种馅儿，每种馅儿做面包需要的面的克数和馅儿的克数以及馅儿的总克数，面也可以单独做面包，然后每一种面包都有价格，求做的面包的总价格最高？

分析：很贱的题目啊，读了之后就开始贪心，贪心竟然过了10组数据，然后我以为有漏洞，后来发现是个多重背包。dp的题目最怕用贪心做了，幸亏发现了。

标准的多种背包，转化一下就行了，n克面就是背包容量，然后每种的数量是馅儿的总量 / 每个的，花费是面的克数，价值是价格。剩下的事情就是模板了、二进制优化一下

AC代码：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <map>
    #include <vector>
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 1200;
    struct Node
    {
        int cost,w,nk; //价格，重量，代数
    };
    Node num[N];
    int dp[N];
    //int cmp(Node a,Node b)
    //{
    //    if(a.p!=b.p)
    //    {
    //        return a.p>b.p;
    //    }
    //}
    void one(int cost , int w, int m)
    {
        for(int i=cost ; i<=m; i++)
            dp[i] = max(dp[i] , dp[i - cost ]+w);
    }
    void zero_one(int m ,int w, int cost)
    {
        for(int i=m; i>=cost; i--)
            dp[i]=max(dp[i],dp[i-cost]+w);
    }
    int main()
    {
        int n,m,a,b;
        scanf("%d%d%d%d",&n,&m,&a,&b);
        num[0].nk=n/a,num[0].cost=b,num[0].w=a;
        for(int i=1; i<=m; i++)
        {
            int x,y,z,h;
            scanf("%d%d%d%d",&x,&y,&z,&h);
            num[i].nk=x/y;
            num[i].cost=h,num[i].w=z;
        }
        for(int i=0; i<=m; i++)
        {
            int w=num[i].cost , cost=num[i].w, nk=num[i].nk;
            if(cost * nk >= n) one(cost , w  , n);
            else
            {
                int k = 1;
                while( k < nk)
                {
                    zero_one(n,k*w,k*cost);
                    nk -= k;
                    k *= 2;
                }
                zero_one(n,nk*w,nk*cost);
            }
        }
        printf("%d\n",dp[n]);
        return 0;
    }

[Codeforces 106 C Buns]: http://codeforces.com/problemset/problem/106/C