Problem N

Problem
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.< br>< br>* 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

题意：这题就是给出第I天生产货物的成本和需要生产的货物数量，并且可生产比需求量更多的数量，但是货物的每天保管费用是5快钱：

思路：就是简单的贪心比较用今天的成本和昨天的成本加上报关费那个便宜，用哪个；

代码：

#include

#include

#define maxn 10000

using namespace std;

int main()

{


//freopen("in.txt", "r", stdin);

    int
n,s,c[maxn],y[maxn];

    long long
money=0,daymoney=0;


while(scanf("%d%d",&n,&s)!=EOF)

    {


money=daymoney=0;


for(int i=0;i


scanf("%d%d",&c[i],&y[i]);


money=c[0]*y[0];


for(int i=1;i


{


daymoney=min(c[i]*y[i],(c[i-1]+s)*y[i]);


//printf("c[i]=%d (c[i-1]+s)=%d\n",c[i],(c[i-1]+s));


//printf("daymoney=%d\n",daymoney);


money+=daymoney;


}


printf("%lld\n",money);

    }

}

巴特西

Problem N

最新文章

热门文章