挑战程序设计竞赛 2.2 poj 2393 Yogurt factory

发布时间 2023-10-03 12:19:56作者: itdef

https://vjudge.net/problem/POJ-2393

奶牛们购买了一家酸奶厂,生产世界闻名的 "Yucky Yogurt "酸奶。在接下来的 N (1 <= N <= 10,000) 周里,牛奶和劳动力的价格每周都会波动,
因此在第 i 周生产一单位酸奶将花费公司 C_i (1 <= C_i <= 5,000) 美分。
Yucky 酸奶厂设计合理,每周可以生产任意多单位的酸奶。

Yucky 酸奶公司拥有一个仓库,可以储存未使用的酸奶,每周每单位酸奶的固定费用为 S(1 <= S <= 100)美分。
幸运的是,酸奶不会变质。Yucky Yogurt 的仓库很大,可以存放任意数量的酸奶。

Yucky 想找到一种方法,每周向客户配送 Y_i (0 <= Y_i <= 10,000)单位的酸奶(Y_i 是第 i 周的配送量)。
请帮助 Yucky 公司在整个 N 周期间尽量降低成本。第 i 周生产的酸奶和已储存的酸奶可用于满足 Yucky 在该周的需求。
输入
* 第 1 行 两个空格分隔的整数 N 和 S。

* 第 2...N+1 行: 第 i+1 行包含两个空格分隔的整数: C_i 和 Y_i。
输出
* 第 1 行: 第 1 行包含一个整数:满足酸奶计划的最小总成本。请注意,对于 32 位整数来说,总成本可能过大。


4 5
88 200
89 400
97 300
91 500


126900

输出详情:
第 1 周,生产 200 件酸奶并全部交付。第 2 周,生产 700 个单位:交付 400 个单位,同时储存 300 个单位。
第 3 周,交付已储存的 300 个单位。第 4 周,生产并交付 500 个单位。

代码

#include <iostream>

using namespace std;
//https://vjudge.net/problem/POJ-2393