首页 > 代码库 > POJ 2393 Yogurt factory【贪心】
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\n",ans); } return 0; }
POJ 2393 Yogurt factory【贪心】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。