百炼2393:Yogurt factory

总时间限制: 1000ms 内存限制: 65536kB

描述

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.

输入

• 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.

输出

• 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.

样例输入

4 5
88 200
89 400
97 300
91 500

样例输出

126900

提示

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.

题目大意

一个工厂在 N 个星期内进行牛奶的生产，每个礼拜可以生产一定量的牛奶。规定第 i 个礼拜每生产 1 单元的牛奶需要花费 $C_i$ 的费用，并且第 i 个礼拜配送 $Y_i$ 单元的牛奶。可能第 i 个星期生产的牛奶无法配送完，需要进行储存，并且每单元牛奶储存每储存一个星期需要花费 S 的费用。现在给定每个星期生产牛奶的费用 $C_i$ 与 配送的牛奶单元数 $Y_i$，需要注意的是配送的 $Y_i$ 可能是前面未配送完的。你需要做的就是找到一种安排，使得费用最少。

解题思路

先考虑第 i 个礼拜配送的牛奶数 $Y_i$，那么这 $Y_i$ 单元的牛奶只有两种可能：

• 这 $Y_i$ 单元的牛奶是第 i 个星期生产的
• 这 $Y_i$ 单元的牛奶是第 i 个星期之前生产的但未配送完的

那么对于上述两种情况，在第 i 个礼拜需要的费用为：

• $C_i\ast Y_i$
• $(S+prev)\ast Y_i$ ，其中 prev 就是其生产的费用

那么，对于每个礼拜都选取上述两种情况中的较小值，就能得到总的最小值，这也就是 贪心。
prev 的操作：

• 如果选择了第一种情况，那么说明之前生产的都配送完了，所以需要把 prev 更新为 C_i
• 如果选择了第二种情况，那么说明当前星期配送的牛奶是转存的，除生产费用外，需要花费额外的存储费 S，因此 prev 更新为 prev+S（这里 +S 是具有连续性的，也就是牛奶被转存多个星期也会被记录到，但是之前的会被当做生产费用计算）

代码

#include <cstdio>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
long long c, y, ans;
int N, S;

int main(){
	scanf("%d %d", &N, &S);
	long long prev = 1e10;
	for(int i = 0; i < N; i++){
		scanf("%lld %lld", &c, &y);
		prev = min(S + prev, c);
		ans += prev * y;
	}
	printf("%lld", ans);
	return 0;
}