[CF106C]Buns

面包师Lavrenty打算用馅料做几个面包，然后把它们卖掉。

Lavrenty有\(n\)克面团和\(m\)种不同的馅料。馅料种类的下标从\(1到m\)，他知道他的第\(i\)种馅料剩下\(a_i\) 克，做一个第\(i\)种馅料的面包，恰恰需要\(b_i\)克的\(i\)种馅料和\(c_i\)克的面团，同时这种面包可以卖\(d_i\)块钱。

他也可以做没有馅的面包。每个这样的面包需要\(c_0\)克面团，可以卖\(d_0\)块Tugrik。所以Lavrenty可以做任何数量的包子，用不同的馅料或者不用馅料，除非用完了面团和馅料。Lavrenty会扔掉烘培面包后剩下的所有多余材料。

求出Lavrenty可以赚取的钱的最大数量。

输入格式

第一行4个整数n,m,\(c_0,d_0\) \(1<=n<=1000,1<=m<=10\)

接下来m行每行四个整数\(a_i,b_i,c_i,d_i\) \(1<=a_i,b_i,c_i,d_i<=100\)

输出格式

输出Lavrenty可以赚取的最大钱数

样例输入

10 2 2 1

7 3 2 100

12 3 1 10

样例输出

241

题解

很好的一道多重背包模板，然而却似乎没有很多人做？

这里放上两份代码，一份详细一份简单

#include<bits/stdc++.h>

#define maxm 50

#define maxn 1500

#define maxa 150

using namespace std;

inline char get(){

	static char buf[3000],*p1=buf,*p2=buf;

	return p1==p2 && (p2=(p1=buf)+fread(buf,1,3000,stdin),p1==p2)?EOF:*p1++;

}

inline int read(){

	register char c=get();register int f=1,_=0;

	while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();

	while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();

	return _*f;

}

int n,m;//n表示面团总数，m表示馅料种类

int a[maxn],d[maxn],b[maxn],c[maxn];

/*

a表示第i种馅料剩余数量

b表示第i种要的馅料数量

c表示第i种要的面团数量

d表示收益

*/

int dp[maxm][maxn];//第一维遍历面包种类，第二维遍历面团

int num;

int note[maxm][maxn];

int main(){

	//freopen("1.txt","r",stdin);

	n=read();m=read();

	c[1]=read();d[1]=read();a[1]=0;b[1]=0;

	//cout<<n<<m<<endl;

	int out=-1;

	for(register int i=2;i<=m+1;i++)a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();

	for(register int i=1;i<=m+1;i++){//遍历面包种类

		for(register int j=0;j<=n;j++){//遍历面团重量

			for(register int k=0;k*b[i]<=a[i] && k*c[i]<=n;k++){

				if(j>=c[i]*k){

                    dp[i][j]=max(dp[i-1][j-c[i]*k]+d[i]*k,dp[i][j]);

                }

			}

			//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;

			out=max(out,dp[i][j]);

		}

	}

	cout<<out<<endl;

	return 0;

}

#include<bits/stdc++.h>

using namespace std;

int n,m;

int a[1500],d[1500],b[1500],c[1500];

int dp[15][1500];

int main(){

	n=read();m=read();

	cin>>c[1]>>d[1];a[1]=0;b[1]=0;

	for(int i=2;i<=m+1;i++)a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();

	for(int i=1;i<=m+1;i++){

		for(int j=0;j<=n;j++){

			for(int k=0;k*b[i]<=a[i] && k*c[i]<=n;k++){

				if(j>=c[i]*k)dp[i][j]=max(dp[i-1][j-c[i]*k]+d[i]*k,dp[i][j]);

			}

			out=max(out,dp[i][j]);

		}

	}

	cout<<out<<endl;

	return 0;

}

巴特西

[CF106C]Buns

输入格式

输出格式

样例输入

样例输出

题解

最新文章

热门文章