POJ 2393 -- Yogurt factory

http://poj.org/problem?id=2393
The cows have purchased a yogurt factory that makes world-famous Yucky Yogurt. Over the next N (1 <= N <= 10,000) weeks, the price of milk and labor will fluctuate weekly such that it will cost the company C_i (1 <= C_i <= 5,000) cents to produce one unit of yogurt in week i. Yucky's factory, being well-designed, can produce arbitrarily many units of yogurt each week.

Yucky Yogurt owns a warehouse that can store unused yogurt at a constant fee of S (1 <= S <= 100) cents per unit of yogurt per week. Fortuitously, yogurt does not spoil. Yucky Yogurt's warehouse is enormous, so it can hold arbitrarily many units of yogurt.

Yucky wants to find a way to make weekly deliveries of Y_i (0 <= Y_i <= 10,000) units of yogurt to its clientele (Y_i is the delivery quantity in week i). Help Yucky minimize its costs over the entire N-week period. Yogurt produced in week i, as well as any yogurt already in storage, can be used to meet Yucky's demand for that week.

Input

* Line 1: Two space-separated integers, N and S.
* Lines 2..N+1: Line i+1 contains two space-separated integers: C_i and Y_i.

Sample Input

4 5
88 200
89 400
97 300
91 500

http://www.hankcs.com/program/cpp/poj-2393-yogurt-factory.html
奶牛们建了一家酸奶厂，在N周内每周需要出货Y_i单位酸奶，第i周成本为C_i，储存费为每周Y。求总体最低成本。
贪心策略是维持每周的最低单位成本，每周可能用上周剩下的，也可能生产新的。于是该周单位成本可能为上一周的单位成本加上储存费，也可能为该周的单位成本。
每天要么以今天的价格买入，要么前面某天买了存在仓库里。不存在一半是今天买的，一半是从仓库拿的，这种情况。
因为如果这样，肯定有一半具有更高的性价比，那就全部都改成更高性价比的方式就好了。。
所以，这题只需要保存一个当前的最大值，扫描一遍就能出结果了。

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int N, S;

    cin >> N >> S;

    int P = 5000;

    long long costs = 0;

    for (int i = 0; i < N; ++i)

    {

        int C, Y;

        cin >> C >> Y;

        P = min(P + S, C);

        costs += P * Y;

    }

    cout << costs << endl;

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

Read full article from 2393 -- Yogurt factory