#|POJ2393 Yogurt factory【贪心】 #|ICPC-贪心法|#|USACO|#|ICPC-POJ|I

Yogurt factory

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 13342		Accepted: 6696

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. 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. 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.
Source
USACO 2005 March Gold

问题链接：POJ2393 Yogurt factory

问题简述：（略）

问题分析：

一个任务，酸奶制造厂在n个星期内连续向外提供酸奶。第i个星期向外提供y[i]单位酸奶，一个单位酸奶的制造费用为c[i]，储存室每个星期储存一个个单位酸奶的费用为s。求完成这个任务的最小费用是多少。
程序说明：
维护一个当前最优（最小）代价即可。

题记：（略）

参考链接：（略）

AC的C++语言程序如下：

/* POJ2393 Yogurt factory */#include #include #include using namespace std; int main() { int n, s, c, y; while(~scanf("%d%d", &n, &s)) { int minc = 10000; long long sum = 0; while(n--) { scanf("%d%d", &c, &y); minc = min(minc + s, c); sum += minc * y; }printf("%lld\n", sum); }return 0; }

【#|POJ2393 Yogurt factory【贪心】】