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 500Sample Output
126900Hint
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代表星期,s代表每单位酸奶储存所需要的金额 下面给出n行 每行有两个整数 第一个整数代表该周生产1单位酸奶所需的金额 第二个整数代表该周酸奶的需求量 我们要求的是最优的生产策略的花费(如何使生产所有的酸奶花费最小) 分析:刚开始的时候准备维护一个优先队列 但是其实不需要使用单调队列 只要我们维护一个最小值即可 那么 每周我们都用我们可以使用金额的最小值来生产 就是最优策略 而这个最小值为: minPrice = min(minPrice + s , week[i]); (week[i]代表该周的金额) 比如本题案例 In week 2, produce 700 units: deliver 400 units while storing 300 units. In week 3, deliver the 300 units that were stored. 由于我们在第三周的价格大于第二周的价格 + 维护费用 所以我们应该在第二周就把第三周的酸奶生产好 然后支付这个维护费用即可 但我们可以换个角度 我们在第二周还是只生产第二周的酸奶 把这个维护费用加在第二周的生产价格上 作为第三周的生产价格 就这样,我们在每周只生产自己的酸奶 只是使用最小的价格 最后就能得到最优的策略 代码: #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; priority_queue<int> q; int week[10000 + 5]; int v[10000 + 5]; int main() { int n,s; long long ans = 0; int amount = 0; int minPrice = 100000000; scanf("%d %d",&n,&s); for(int i = 0;i<n;i++) { scanf("%d %d",&week[i],&v[i]); int pri = minPrice; minPrice = min(minPrice + s , week[i]); ans += (minPrice * v[i]); } printf("%lld\n",ans); }