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.
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
",c[i],(c[i-1]+s));
//printf("daymoney=%d
",daymoney);
money+=daymoney;
}
printf("%lld
",money);
}
}
#include
#define maxn 10000
using namespace std;
int main()
{
}