CODEVS1260 快餐问题
1260 快餐问题
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。价格便宜。为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡、薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡、薯条和饮料的单位生产时间又不同，这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编写程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。
输入描述 Input Description
第一行为三个不超过100的正整数A、B、C，中间以一个空格分开；
第二行为三个不超过100的正整数p1、p2、p3分别为汉堡、薯条和饮料的单位生产耗时。中间以一个空格分开。
第三行为一个整数N(0≤N≤10)代表流水线；
第四行为M个不超过10000的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。
输出描述 Output Description
输出文件仅一行，即每天套餐的最大产量。
样例输入 Sample Input
1 2 1
1 2 1
5
16 16 8 9 14
样例输出
Sample Output
1、20172319 实验五 《网络编程与安全》实验报告
2、Linux下Mysql安装（tar安装）
3、Cannot read property 'setState' of undefined
4、教大家一个赚支付宝红包的技巧一天我赚了600了
5、2018.10.22【COGS2633】数列操作e（线段树）
10
【题解】
dp[i][j][k]表示前i条流水线生产j个汉堡k个薯条后最多生产多少杯饮料，转移显然
题目中有限制，最多生产100
所以计算最大汉堡/薯条/饮料时要对100取一个min
采用倒序枚举状态，如果前i-1条流水线枚举不到j,k，说明此时饮料已经超了，后面的
更不可能枚举到j,k，一定会比j,k大
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #define max(a, b) ((a) > (b) ? (a) : (b)) 6 #define min(a, b) ((a) < (b) ? (a) : (b)) 7 8 inline void read(int &x) 9 { 10 x = 0;char ch = getchar(), c = ch; 11 while(ch < '0' || ch > '9')c = ch, ch = getchar(); 12 while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar(); 13 if(c == '-')x = -x; 14 } 15 16 const int MAXN = 100 + 5; 17 18 int a,b,c,p1,p2,p3,n,dp[MAXN][MAXN][MAXN],t[MAXN]; 19 //dp[i][j][k]表示前i条流水线，生产j个汉堡，k个薯条，能生产多少饮料 20 21 int ma,sum,ans; 22 //最多生产多少套 23 24 int main() 25 { 26 read(a), read(b), read(c); 27 read(p1), read(p2), read(p3); 28 read(n); 29 for(register int i = 1;i <= n;++ i) read(t[i]), sum += t[i]; 30 ma = sum / (a * p1 + b * p2 + c * p3); 31 int tmp1 = min(100, ma * a), tmp2 = min(100, ma * b), tmp3 = min(100, ma * c); 32 for(register int i = 1;i <= n;++ i) 33 for(register int j = tmp1;j >= 1;-- j) 34 for(register int k = tmp2;k >= 1;-- k) 35 { 36 for(register int jj = j;jj >= 1;-- jj) 37 { 38 for(register int kk = k;kk >= 1;-- kk) 39 { 40 dp[i][j][k] = max(dp[i][j][k], dp[i - 1][jj][kk] + (t[i] - (j - jj)*p1 - (k - kk)*p2)/p3); 41 if(dp[i][j][k] > 100)break; 42 } 43 if(dp[i][j][k] > 100)break; 44 } 45 ans = max(ans, min(j/a, min(k/b, dp[i][j][k]/c))); 46 if(dp[i][j][k] > 100)break; 47 } 48 printf("%d", ans); 49 return 0; 50 }CODEVS1260 优质内容筛选与推荐>>
1、20172319 实验五 《网络编程与安全》实验报告
2、Linux下Mysql安装（tar安装）
3、Cannot read property 'setState' of undefined
4、教大家一个赚支付宝红包的技巧一天我赚了600了
5、2018.10.22【COGS2633】数列操作e（线段树）