贪心等 [Cloned] T"/>
二、stl ,模拟,贪心等 [Cloned] T
原题:
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.
题意:
一个生产酸奶的工厂,每天生产的量是可以根据情况改变,但是每天生产的成本不同,同时之前生产的酸奶可以无限期储存,但是储存每天有成本。因为每天要收购的量是不同的,要求出成本最低的生产方式,也就是要么在成本低的时候生产再加上储存的价格,还是直接在当天生产。
题解:
不断更新是这一天当天生产便宜还是之前生产储存便宜,因为上一天选择的也是当天便宜的方法,所以只需要每次更新上一天的加上一天的储存成本和当天生产哪一个更便宜就可以,贪心当天最便宜的方法,也就为以后的天数提供了可能的便宜方法。
代码:AC
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
long long min(long long a,long long b)
{if(a<b)return a;elsereturn b;
}
int main()
{int n,s;cin>>n>>s;long long sum=0,t=0;int i,c,y;for(i=0;i<n;i++){cin>>c>>y;if(i==0){t=(long long )c;}else{t=min(t+s,(long long )c);}sum+=t*y;}cout<<sum<<endl;return 0;
}
更多推荐
二、stl ,模拟,贪心等 [Cloned] T
发布评论