Yogurt factory 贪心算法

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

 

题目大意：有一个酸奶工厂，他要向客户供奶，一共有n周，但是生产酸奶的单位价格每一周都不一样，他有一个仓库，可以保存酸奶，每保存一周有固定的保存费用s，现在给出n周的每周生产单位酸奶的价格和每周要和客户供奶的量，求最小花费是多少

 

开始复杂算法是从最后一个开始，看这一个在哪周生产合适，然后算这一周（最后一周）的花费。复杂度（N*N）

正确的算法是 从第一天 (a i ) 开始算之后每天 

 

1，第一天的奶只能当天生产，暂时假设以后的奶全在这一天生产

2，第二天的话，比较今天和昨天 如果当天生产比较省钱，那么就当天生产,而且假设以后的所有奶都在这天生产的（需要你好好思考一下）