POJ 2393 Yogurt factory【贪心】

题意：

每周可以生产牛奶，每周生产的价格为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\n",ans);

    }

    return 0;

}

巴特西

POJ 2393 Yogurt factory【贪心】

最新文章

热门文章