【题解】POJ 2393 Yogurt factory(贪心)

POJ 2393 Yogurt factory

---

原题

https://vjudge.net/problem/POJ-2393

奶牛们购买了一家酸奶厂，生产世界闻名的Yucky酸奶。在接下来的N (1 < = N < = 10000)周,牛奶的价格和劳动力的成本波动每周,这样它将公司为C_i(1 < =为C_i < = 5000)分在星期我生产一个单位的酸奶,
Yucky的工厂,是精心设计的,可以产生任意的许多单位每周酸奶。
Yucky酸奶拥有一个仓库，可以储存不用的酸奶，每周每单位的固定费用是S (1 <= S <= 100)美分。幸运的是，酸奶不会变质。Yucky酸奶的仓库非常大，所以它可以容纳任意多单位的酸奶。
Yucky希望找到一种方法，每周向顾客运送Y_i (0 <= Y_i <= 10,000)个酸奶(Y_i是第一周的运送量).帮助Yucky在整个n周内将成本降到最低。第一周生产的酸奶，以及任何已经储存的酸奶，都可以满足Yucky那一周的需求。
输入:
第1行:两个以空格分隔的整数，N和S。
第2~N+1:第i+1行包含两个以空格分隔的整数:C_i和Y_i。
输出：
第1行:第1行包含一个整数:满足酸奶计划的最小总成本。注意，对于32位整数来说，总数可能太大了。
Sample Input

4 5
88 200
89 400
97 300
91 500

Sample Output

126900

提示。
输出细节:在第一周，生产200个单位的酸奶，并交付所有。在第二周，生产700件:交付400件，储存300件。在第三周，交付储存的300个单元。在第4周，生产并交付500件。

---

题解

题意：每周的生产成本是有波动的，储存成本固定，已知每周的供应量，求最小成本。
思路：很显然我们希望每周交付的酸奶的成本都是最小的，通过比较当前的生产成本和之前的生产成本加储存成本，哪个便宜就用哪个。具体见代码。

#include<iostream>
#define ll long long

using namespace std;
const int Maxn = 10000 + 10;
int c[Maxn], y[Maxn];
int main() {
	
	int n, s;
	cin >> n >> s;
	for(int i = 0; i < n; i++)
		cin >> c[i] >> y[i];
	for(int i = 1; i < n; i++)
		c[i] = min(c[i], c[i - 1] + s);//每两周比较一次，最后得到每周的最小成本
	ll sum = 0;//32位存不下
	for(int i = 0; i < n; i++)
		sum += c[i] * y[i];//直接成本乘数量
	cout << sum << endl;
	return 0;
}