贪心】Yogurt factory POJ"/>
【原创】【贪心】Yogurt factory POJ
Yougurt Factory
题目
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.
题意
有N周,每周都要交付Yi的酸奶,而每周生产酸奶的价格是Ci每单位。多生产的酸奶可以保存在仓库(不会放坏的放心)里,而仓库也要花钱,价格是一个常量S每单位每周。求最小费用。
分析
这题的思路比较神奇。(每周不方便,就说每天)
我们来看每一天的酸奶。要交付Yi个单位,这Yi个从哪里来?
有且仅有两种方式:
①今天生产
②以前的某天生产并保存到今天
想要让总费用最小,只要让每天的费用尽可能小就OK了。
那么今天的费用就为:
Y[i]*min{C[i],C[i-1]+S,C[i-2]+S*2,....,C[1]+S*(i-1)}
感觉变成了DP?
其实,因为S是常量,所有后面那一坨的最小值(就是min里除C[i]外的所有)我们可以预处理出来。
比如说到了第2天,价格=min{C[2],C[1]+s}
,我们把这个值保存下来,假设为k。第3天,价格=min{C[3],C[2]+s,C[1]+s+s}
,其实就是min{C[3],k+s}
,因为在不等式两边加上同样的值,不等式仍然成立。
以此类推,今后每一天的价格都可以很快的求出来了。
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;void Read(int &p)
{p=0;char c=getchar();while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9')p=p*10+c-'0',c=getchar();
}int n,s,c,y,minic=0x7fffffff;
long long ans;
int main()
{Read(n); Read(s);for(int i=1;i<=n;i++){Read(c),Read(y);minic=min(c,minic);ans+=minic*y;minic+=s;}cout<<ans<<endl;
}
更多推荐
【原创】【贪心】Yogurt factory POJ
发布评论