| 题目名称 | 194. [USACO Mar03] 奶酪工厂 |
|---|---|
| 输入输出 | factory.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2008-11-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：103， 提交：209， 通过率：49.28% | ||||
 龙征天 |
100 | 0.000 s | 0.00 MiB | C++ |
 Eddy2008 |
100 | 0.000 s | 0.00 MiB | C++ |
 devil |
100 | 0.010 s | 0.31 MiB | C++ |
 mzy |
100 | 0.011 s | 0.31 MiB | C++ |
 HouJikan |
100 | 0.011 s | 0.39 MiB | C++ |
 TBK |
100 | 0.011 s | 2.83 MiB | C++ |
 Satoshi |
100 | 0.012 s | 0.39 MiB | C++ |
 4154 |
100 | 0.013 s | 0.14 MiB | Pascal |
|
HouJikan |
100 | 0.013 s | 3.23 MiB | C++ |
 超级腻害的小蝶子 |
100 | 0.014 s | 0.24 MiB | Pascal |
| 本题关联比赛 | |||
| noip20081103 | |||
| 20200701 | |||
| 关于 奶酪工厂 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
贪最小单价就行了，O(n^2)算法，结果要long long
 Dream
2016-02-22 00:28
5楼
| ||||
|
O(n^2)的算法都能过。。。。。
当然我用的O(n) | ||||
|
好大的范围。。。
前面输出用长整，结果不够用。 超级腻害的小蝶子
2012-10-25 18:50
3楼
| ||||
|
思路简单，可以倒着考虑，贪心O(n2)可过
问题是，读入都得long long，坑爹啊！ | ||||
|
算法很简单的，你能想到的，亲！
只不过，要用long long； 呵呵！ | ||||
iortheir
Truth.Cirno
苏轼【问题描述】
奶牛们开办了一个奶酪工厂来生产世界著名的约克奶酪。在接下来的 N (1<=N<=10000) 星期中，由于牛奶和劳动力的价格变化，奶酪的成本也在变化。因此奶酪工厂在第 i 个星期要花 C_i (1<=C_i<=5000) 分来生产一个单位的奶酪。 由于采用了最先进的技术，约克奶酪工厂在一个星期内可以生产任意多的奶酪。
约克奶酪工厂拥有一个无限大的仓库， 每个星期生产的多余的奶酪都会放在这里。而且每个星期存放一个单位的奶酪要花费 S (1<=S<=100) 分，不过幸运的是由于采用了最先进的技术，奶酪在仓库里不会坏 ^_^
工厂最近收到了客户 N 个星期的订单，第 i 个星期要向客户提供 Y_i (0<=Y_i<=10000) 个单位的奶酪。当然这些奶酪可以在第 i 个星期时生产，也可以从仓库中拿取。
采用怎么样的生产策略才会使约克工厂的花费最小呢？你能帮帮它们吗？
【输入格式】
第 1 行两个整数： N 和 S
接下来的 N 行中，第 i 行的两个数表示： C_i 和 Y_i
【输出格式】
输出仅一行，工厂生产的最小花费。
【输入样例】
4 5 88 200 89 400 97 300 91 500
【输出样例】
126900
【输入输出样例说明】
最佳生产方案如下：第一个星期生产 200 个单位的奶酪全部送给客户，第二个星期生产 700 个单位的奶酪， 400 个送给客户，另外 300 个放在仓库。第三个星期把仓库中的 300 个奶酪卖给客户，第四个星期生产 500 个单位的奶酪卖给客户。