POJ2393 Yogurt factory 【贪心】
2024-08-31 00:35:30
Yogurt factory
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 6821 | Accepted: 3488 |
Description
The cows have purchased a yogurt factory that makes world-famous Yucky Yogurt. Over the next N (1 <= N <= 10,000) weeks, the price of milk and labor will fluctuate weekly such that it will cost the company C_i (1 <= C_i <= 5,000) cents to produce one unit of
yogurt in week i. Yucky's factory, being well-designed, can produce arbitrarily many units of yogurt each week.
Yucky Yogurt owns a warehouse that can store unused yogurt at a constant fee of S (1 <= S <= 100) cents per unit of yogurt per week. Fortuitously, yogurt does not spoil. Yucky Yogurt's warehouse is enormous, so it can hold arbitrarily many units of yogurt.
Yucky wants to find a way to make weekly deliveries of Y_i (0 <= Y_i <= 10,000) units of yogurt to its clientele (Y_i is the delivery quantity in week i). Help Yucky minimize its costs over the entire N-week period. Yogurt produced in week i, as well as any
yogurt already in storage, can be used to meet Yucky's demand for that week.
yogurt in week i. Yucky's factory, being well-designed, can produce arbitrarily many units of yogurt each week.
Yucky Yogurt owns a warehouse that can store unused yogurt at a constant fee of S (1 <= S <= 100) cents per unit of yogurt per week. Fortuitously, yogurt does not spoil. Yucky Yogurt's warehouse is enormous, so it can hold arbitrarily many units of yogurt.
Yucky wants to find a way to make weekly deliveries of Y_i (0 <= Y_i <= 10,000) units of yogurt to its clientele (Y_i is the delivery quantity in week i). Help Yucky minimize its costs over the entire N-week period. Yogurt produced in week i, as well as any
yogurt already in storage, can be used to meet Yucky's demand for that week.
Input
* Line 1: Two space-separated integers, N and S.
* Lines 2..N+1: Line i+1 contains two space-separated integers: C_i and Y_i.
* Lines 2..N+1: Line i+1 contains two space-separated integers: C_i and Y_i.
Output
* Line 1: Line 1 contains a single integer: the minimum total cost to satisfy the yogurt schedule. Note that the total might be too large for a 32-bit integer.
Sample Input
4 5
88 200
89 400
97 300
91 500
Sample Output
126900
Hint
OUTPUT DETAILS:
In week 1, produce 200 units of yogurt and deliver all of it. In week 2, produce 700 units: deliver 400 units while storing 300 units. In week 3, deliver the 300 units that were stored. In week 4, produce and deliver 500 units.
In week 1, produce 200 units of yogurt and deliver all of it. In week 2, produce 700 units: deliver 400 units while storing 300 units. In week 3, deliver the 300 units that were stored. In week 4, produce and deliver 500 units.
Source
每次更新相邻的下一周就可以。由于若下一周被更新,那么下一周能够用来更新剩下的周,所以当前周仅仅须要负责下一周。
#include <stdio.h>
#include <string.h> #define maxn 10002 int min(int a, int b) {
return a < b ? a : b;
} int X[maxn], Y[maxn]; int main() {
int N, S, i, j;
__int64 sum;
while(scanf("%d%d", &N, &S) == 2) {
for(i = 0; i < N; ++i)
scanf("%d%d", &X[i], &Y[i]);
for(i = sum = 0; i < N; ++i) {
sum += X[i] * Y[i];
if(i != N - 1)
X[i+1] = min(X[i+1], X[i] + S);
}
printf("%I64d\n", sum);
}
return 0;
}
2014-12-1更新
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL; LL ans; int main() {
int N, S, i, c, m, pre;
scanf("%d%d", &N, &S);
scanf("%d%d", &c, &m);
pre = c + S; // 仓库价格
ans += c * m;
while(--N) {
scanf("%d%d", &c, &m);
if(pre < c) c = pre;
else pre = c;
ans += c * m;
pre += S;
}
printf("%lld\n", ans);
return 0;
}
最新文章
- form表单的字符串进行utf-8编码
- iOS UIWebView 拦截点击事件(双击缩放)
- Apworks框架实战(二):开始使用
- JS获取指定的cookie值
- NSUserDefaults 可以保存哪些类型
- JavaScript学习总结【1】、初识JS
- [转] 「指尖上的魔法」 - 谈谈 React Native 中的手势
- BZOJ 1564: [NOI2009]二叉查找树( dp )
- 查看SQL SERVER 加密存储过程,函数,触发器,视图
- 创建免费的证书,实现网站HTTPS
- django 中自带的加密方法
- 设计模式---策略模式Strategy(对象行为型)
- C语言引用连接脚本lds中的符号——清除bss段,c实现方式
- JS继承封装
- 为Jquery类和Jquery对象扩展方法
- G - Game HDU - 5242 (数链剖分)
- oracle 查询优化及sql改写
- scrapy框架 小知识
- iOS- 网络访问JSON数据类型与XML数据类型的实现思路及它们之间的区别
- 个人作业4 alpha阶段 个人总结
热门文章
- Angular——配置模块与运行模块
- Understanding and Analyzing Application Crash Reports
- 并发编程学习笔记(14)----ThreadPoolExecutor(线程池)的使用及原理
- 【转载】Spring注解@Resource和@Autowired区别对比
- A6. JVM 垃圾回收算法(GC 算法)
- java.net.MalformedURLException: no protocol: www.baidu.com
- 面试总结——Java高级工程师(二)
- Session共享实现方案调研
- 后台工具screen
- [bzoj4591][Shoi2015][超能粒子炮&#183;改] (lucas定理+组合计数)