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

解题思路:每一周有两种选择

1.只生产本周的牛奶量

2.生产本周和下一周的牛奶量，这样下一周就不用生产直接卖掉

这就需要这两种情况对比一下

设两个变量tmp1和tmp2，tmp1代表只单生产本周的牛奶加上只单生产下一周的牛奶所花费的成本。tmp2代表生产本周和下一周的牛奶再加上存储下一周的牛奶所花的存储费用。

如果tmp1>tmp2，就说明本周应该也生产下一周的牛奶。然后计算出来到目前为止本周的成本，同时下一周不用生产，下一周的成本和上一周一样。

如果tmp1<=tmp2,就只生产本周的牛奶。

dp数组是递推得出的，dp【n】就是最终的答案。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 10002
ll dp[N];

ll n, S;

struct node
{
	ll price;
	ll count;
}milk[10002];
int main()
{
	cin >> n >> S;
	for (int i = 1; i <= n; i++)
		cin >> milk[i].price >> milk[i].count;

	for (int i = 1; i <= n;i++)
	{
		ll tmp1 =milk[i].count*milk[i].price+ milk[i+1].count*milk[i+1].price;
		ll tmp2 = (milk[i + 1].count + milk[i].count)*milk[i].price + milk[i + 1].count*S;
		if (tmp1 > tmp2)
		{			dp[i] = tmp2 + dp[i-1];//递推一下，得出到本周的所有成本
			dp[i + 1] = dp[i];//下一周的目前总成本和本周的目前总成本一样
			i++;
		}
		else
			dp[i] = dp[i - 1] + milk[i].price*milk[i].count;//递推一下，得出到本周的所有成本
	}

	cout << dp[n] << endl;
	return 0;
}