POJ 2393 Yogurt factory

题目链接：点击打开链接

Yogurt factory Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 13459 Accepted: 6753

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

Source

USACO 2005 March Gold

#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; long long i,j,n,s,k,ans,c[20000],y[20000],a[20000],sum[20000],min1; int main() { scanf("%lld%lld",&n,&s); for (i=1;i<=n;i++) scanf("%lld%lld",&c[i],&y[i]); for (i=1;i<=n;i++) sum[i]=c[i]-s*i; min1=0x3f3f3f3f; k=0; for (i=1;i<=n;i++) { if (sum[i]>min1) a[i]=k; else a[i]=i; if (sum[i]<min1) { min1=sum[i]; k=i; } } ans=0; for (i=1;i<=n;i++) { if (a[i]==i) ans+=c[i]*y[i]; else ans+=c[a[i]]*y[i]+s*(i-a[i])*y[i]; } printf("%lld",ans); return(0); }

PS：当前week i的果汁总共有两种操作，一个是这周做好，一个是前面预先做好，到底选择哪个方案呢？

1.如果本周做好，花费为c[i]*y[i]；

2.如果在前面week j做好，肯定是在前面week j先做好比在本周做更优的情况下，也就是满足c[j]*y[i]+(j-i)*s*y[i]<c[i]*y[i]（式1），我们选择j（j<=i）中使得c[j]*y[i]+(j-i)*s*y[i]最小的一个。

如果采用暴力手段，会超时。

这时我们注意到式1两边可以同时约去y[i]，式1就变成了c[j]+(j-i)*s<c[i]，也就是c[j]+j*s<c[i]+s*i，所以我们预处理sum数组等于c[i]+s*i，一遍for循环即可！

做题不要慌，慢慢来，祝大家刷题顺利！加油！