POJ 2393 Yogurt factory【贪心】

POJ 2393

题意:

每周可以生产牛奶,每周生产的价格为Ci,每周需要上交的牛奶量Yi,你可以选择本周生产牛奶,也可选择提前几周生产出存储在仓库中(仓库无限大,而且保质期不考虑),每一周存仓库牛奶需要花费S元,让你求出所有周的需求量上交的最少花费。

分析:

因为第 i 周的奶酪,可以在第 i 周生产,也可以在前几周生产,然后储存。通过把s转化为花费,跟原有花费去比较,取一个最小值,这样从头到尾,每一周都可以取得一个花费的最小值。贪心求解。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=10011;
int n,s;
int y[maxn],c[maxn];
int main()
{
    while(scanf("%d%d",&n,&s)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%d%d",&c[i],&y[i]);
        long long ans=0;
        for(int i=1;i<n;i++)
            c[i]=min(c[i-1]+s,c[i]);
        for(int i=0;i<n;i++)
            ans+=c[i]*y[i];
        printf("%lld
",ans);
    }  
    return 0;  
}
原文地址:https://www.cnblogs.com/demian/p/6560876.html