POJ 2393 贪心
http://poj.org/problem?id=2393
奶牛们收购了一家世界著名的酸奶工厂Yucky Yogurt. 在接下来的 N (1 <= N <= 10,000) 周,牛奶和人工的价格每周会波动，以致于第i周需要花公司 C_i (1 <= C_i <= 5,000) 美分来生产一个单位的酸奶. Yucky factory被奶牛们照顾得很好，所以每周可以生产很多单位的酸奶
Yucky Yogurt 拥有一个仓库，可以以S (1 <= S <= 100)美分每单位每周的价格储存没用的酸奶。神奇的是，酸奶不会变质。而且仓库十分巨大，可以容纳很多牛奶
Yucky Yogurt每周要交货 Y_i (0 <= Y_i <= 10,000) 单位的酸奶给它的客户。请你帮助奶牛们减少整个 N-week 期间的支出. i周生产的牛奶和之前储存的牛奶都可以用来交i周的货
Input
* 第一行：N and S.
* 第 2..N+1行:第 i+1 行包括 : C_i 和 Y_i.
Output
* 满足客户需求的最小花费，保证不超过64位整数
Sample Input
4 5 88 200 89 400 97 300 91 500
Sample Output
126900
Hint
输出提示:
第一周生产200单位，全部售出。第二周生产700单位，售出400，储存300.第三周使用储存的300单位。第四周，生产500单位并全部售出
注释：
yucky意为难以下咽的
思路：贪心，第一周单价只能是c1；第二周的单价可以是c1+s，c2；第三周的单价可以是：c1+2*s，c2+s，c3……那么贪最少的就行了，复杂度O(n^2)，可以过掉这道题。当然还有改进方法。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
struct node
{
int c,y;
};
int n,s;
node a[10005];
ll sum=0,MIN=0;
int idx;
int main()
{
scanf("%d %d",&n,&s);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&a[i].c,&a[i].y);
MIN=a[i].c;
for(int j=i-1;j>=1;j--)
{
if(a[j].c+(i-j)*s<MIN)
MIN=a[j].c+(i-j)*s;
}
sum+=MIN*a[i].y;
}
printf("%lldn",sum);
return 0;
}
改进算法，通过上面的分析， 我们知道c[i]=min(c[i-1]+s，c[i])， 因此可以0(n)处理出最优的c数组， 复杂度可以降到O(n)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,s;
int c[10005];
int p[10005];
ll sum=0;
int main()
{
scanf("%d %d",&n,&s);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&c[i],&p[i]);
if(i>1)
c[i]=min(c[i],c[i-1]+s);
sum+=c[i]*p[i];
}
printf("%lldn",sum);
return 0;
}
相关知识
【贪心】605. 种花问题
跑趴季／达人教你3招变出派对桌花 重点1：千万别贪心
力扣605.种花问题
正则表达式（regex）实现模式匹配
贪心算法练习
花园的秘密
Leetcode刷题笔记 605. 种花问题
Leetcode 题解
抚州市人民政府 政府重点工作 中国十大名花排行榜，哪个才是你的最爱？
2013年房山区向日葵品种展示.ppt
网址: POJ 2393 贪心 https://m.huajiangbk.com/newsview173960.html
| 上一篇: 没有光照就种这几种花，据说灯光就 |
下一篇: 养花阳光不足用什么灯 |
