Codeforces--106C--Buns(背包)
Time Limit: 2000MS | Memory Limit: 262144KB | 64bit IO Format: %I64d & %I64u |
Description
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.
Sample Input
10 2 2 1
7 3 2 100
12 3 1 10
241
100 1 25 50
15 5 20 10
200
Sample Output
Hint
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种佐料,n克的面粉每c0克可以生成d0价值的产品,同时也可以与任意一种b克佐料混合生成d价值的产品,问这些东西最多制成多少价值的产品
dp[ i ][ j ][ k ],表示i种佐料使用j*c克混合k克面粉生成的价值,第i种佐料我们可以使用for循环控制,j*b克的i面粉跟k克的佐料是对应的,也就是说dp的值是由最后一维控制的,所以j*b也可以由循环表示,所以最后的dp是一维的
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[10000+10];
int main()
{
int n,m,c0,d0;
cin>>n>>m>>c0>>d0;
memset(dp,0,sizeof(dp));
for(int i=c0;i<=n;i++)
dp[i]=i/c0*d0;
int a,b,c,d;
for(int i=0;i<m;i++)
{
cin>>a>>b>>c>>d;
for(int j=1;j<=a/b;j++)//使用i最多生成a/b个合成品
{
for(int k=n;k>=c;k--)
dp[k]=max(dp[k-c]+d,dp[k]);
}
}
cout<<dp[n]<<endl;
return 0;
}
最新文章
- MySql 获取表的字段名
- c# winform 调用js
- java基础-jdbc——三种方式加载驱动建立连接
- Ibatis学习总结1--ibatis简介和SQL Maps
- mysql数据库问答
- cocos2dx系列笔记(2)- windows环境配置后续之 Android环境配置
- hadoop结构出现后format变态
- android删除文件出错
- 在线maven仓库
- Mysql安装设置建议(参数设置)
- 微软开发者大会:VS 2019 Preview 发布;Windows UX 主要技术开源
- LODOP、C-Lodop简短排查语句
- python虚拟环境virtualenv简介
- Azure 元数据服务:适用于 Windows VM 的计划事件(预览)
- python学习之算法、自定义模块、系统标准模块(上)
- hdu 5724-Chess(状态压缩+sg函数)
- Xcode的多种Build Configuration
- CSS链接的样式a:link,a:visited,a:hover,a:active
- HDU 5213 分块 容斥
- RabbitMQ (十三) 集群+单机搭建(window)