Yogurt factory
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 8205 | Accepted: 4197 |
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.
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.
题目是说你每周可以生产牛奶，每周生产的价格为Ci，每周需要上交的牛奶量Yi，你可以选择本周生产牛奶，也可选择提前几周生产出存储在仓库中（仓库无限大，而且保质期不考虑），每一周存仓库牛奶需要花费S元，让你求出所有周的需求量上交的最少花费。
贪心，看了discuss发现只需要考虑邻近的一周，如果a[i].c+s<a[i+1].c，那么本周就把下一周的任务也完成掉。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct node
{
int c,y;
}a[+];
int main()
{
int n,s;
int i;
long long sum;
//freopen("in.txt","r",stdin);
while(scanf("%d%d",&n,&s)!=EOF)
{
for(i=;i<n;i++)
scanf("%d%d",&a[i].c,&a[i].y);
int sto=;
sum=;
for(i=;i<n-;i++)
{
if(sto==a[i].y)
sto=;
else
sum+=a[i].c*a[i].y;
if((a[i].c+s)<a[i+].c)
{
sum+=(a[i].c+s)*a[i+].y;
sto=a[i+].y;
}
}
if(sto!=a[n-].y)
sum+=a[n-].c*a[n-].y;
printf("%lld\n",sum);
} }
简单DP:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct node
{
int c,y;
}a[+];
int main()
{
int n,s;
int i;
long long sum;
freopen("in.txt","r",stdin);
while(scanf("%d%d",&n,&s)!=EOF)
{
sum=;
for(i=;i<n;i++)
scanf("%d%d",&a[i].c,&a[i].y);
for(i=;i<n;i++)
a[i].c=min(a[i].c,a[i-].c+s);
for(i=;i<n;i++)
sum+=a[i].c*a[i].y;
printf("%lld\n",sum);
} }