O - Buns（混合背包）

雨点打透心脏的1/2处 2022-02-23 03:36 157阅读 0赞

### 题目描述： ###

Lavrenty, a baker, is going to make several buns with stuffings and sell them.

Lavrenty has n grams of dough as well as m different stuffing types. The stuffing types are numerated from 1 to m. Lavrenty knows that he has ai grams left of the i-th stuffing. It takes exactly bi grams of stuffing i and ci grams of dough to cook a bun with the i-th stuffing. Such bun can be sold for di tugriks.

Also he can make buns without stuffings. Each of such buns requires c0 grams of dough and it can be sold for d0 tugriks. So Lavrenty can cook any number of buns with different stuffings or without it unless he runs out of dough and the stuffings. Lavrenty throws away all excess material left after baking.

Find the maximum number of tugriks Lavrenty can earn.  
Input

The first line contains 4 integers n, m, c0 and d0 (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10, 1 ≤ c0, d0 ≤ 100). Each of the following m lines contains 4 integers. The i-th line contains numbers ai, bi, ci and di (1 ≤ ai, bi, ci, di ≤ 100).  
Output

Print the only number — the maximum number of tugriks Lavrenty can earn.  
Examples  
Input

10 2 2 1  
7 3 2 100  
12 3 1 10

Output

241

Input

100 1 25 50  
15 5 20 10

Output

200  
Note  
To get the maximum number of tugriks in the first sample, you need to cook 2 buns with stuffing 1, 4 buns with stuffing 2 and a bun without any stuffing.  
In the second sample Lavrenty should cook 4 buns without stuffings.

##### 题意： #####

题目第一行给出n，m，x，y；  
四个数，分别表示n克面粉， m种有馅料的面包。 x，y表示没有馅料的面包所需要的面粉和售价。  
接下来m行，每行给出每种有馅料的面包的基本情况。  
a，b，c，d。  
分别表示，馅料有a克，做一个这样的馅料面包要b克馅料。c克面粉。售价d元。

分析：  
这个题有馅料的面包能做的个数是有限制的，被面粉数量和馅料数量限制。  
没有馅料的面包能做的个数，仅被面粉数量限制。  
我们可以先不考虑面粉数量限制。  
那么这个题的基本思路就将有馅料的面包当作多重背包。  
没有馅料的面包当作完全背包。  
看数据范围都比较小。 那么可以不用优化。

#include"stdio.h"
    #include"string.h"
    #include"functional"
    #include"iostream"
    #include"algorithm"
       using namespace std;
    typedef long long ll;
    #define scanll(a,b) scanf("%I64d%I64d",&a,&b);
    #define scanl(a) scanf("%I64d",&a);
    #define scanff(a,b) scanf("%lf%lf",&a,&b);
    #define scan1f(a) scanf("%lf",&a);
    #define prinll(a,b) printf("%I64d %I64d",a,b);
    #define prinl(a) printf("%I64d",a);
    #define printff(a,b) printf("%lf %lf",a,b);
    #define printlf(a) printf("%lf",a);
    #define OK printf("\n");
    #define MAXSIXE 100100
    ll dp[MAXSIXE];
    struct Good
    {
      ll p;
      ll v;
      ll cnt;
    }goods[11];
    int main()
    {
        ll n,m,x,y;
        scanll(n,m);
        scanll(x,y);
        for(ll i = 1; i <= m; i ++)
        {
            ll a,b,c,d;
            scanll(a,b); scanll(c,d);
            ll cnt = a / b <  n / c ? a / b : n / c;
            goods[i] = {d, c ,cnt};
          //  printf("%lld %lld %lld \n",goods[i].p,goods[i].v,goods[i].cnt);
        }
        //完全背包。没有馅料的面包
        for(ll j = x; j <= n; j ++) dp[j] = dp[j - x] + y;
        //多重背包
        for(ll i = 1; i <= m; i ++)
        {
            for(ll j = n; j >= goods[i].v; j --)
            {
                for(ll k = 0; k <= goods[i].cnt; k ++)
                {
                    if(j >= k * goods[i].v)
                        dp[j] = max(dp[j],dp[j - k * goods[i].v] + k * goods[i].p);
                }
            }
        }
        printf("%lld\n",dp[n]);
    }