Yogurt factory·贪心

题目信息

The cows have purchased a yogurt factory that makes world-famous Yucky Yogurt. Over the nextN (1 <= N <= 10,000)weeks, the price of milk and labor will fluctuate weekly such that it will cost the companyCi (1 <= Ci <= 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 ofS (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 ofYi (0 <= Yi <= 10,000)units of yogurt to its clientele (Yi 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.
奶牛们购买了一家酸奶厂，生产世界著名的美味酸奶。在接下来的N(1 <= N <= 10000) 周内，牛奶和劳动力的价格将每周波动，因此公司在第一周生产一单位酸奶将花费Ci(1<=Ci<=5000)美分。Yucky的工厂设计精良，每周可以生产任意多单位的酸奶。
Yucky酸奶公司拥有一个仓库，可以储存未使用过的酸奶，每单位酸奶每周的固定费用是 S（1<=S<=100）美分。碰巧，酸奶不会变质。Yucky酸奶的仓库是巨大的，所以它可以容纳任意多个单位的酸奶。
Yucky想找到一种方法，每周向客户交付Yi(0 <= Yi <= 10000)单位的酸奶（Yi是第一周的交付量）。帮助Yucky在整个N周期间将成本降至最低。第一周生产的酸奶，以及任何已经储存的酸奶，都可以用来满足那个星期的需求。

输入

Line 1: Two space-separated integers, N and S.
Lines 2…N+1: Line i+1 contains two space-separated integers: Ci and Yi.
第1行：两个空格分隔的整数，N和S。
第2…N+1行：第i+1行包含两个空格分隔的整数：Ci和Yi。

输出

Line 1 contains a single integer: the minimum total cost to satisfy the yogurt schedule. Note that the total might be too large for a 32-bit integer.
第1行包含一个整数：满足计划的最小总成本。请注意，对于32位整数来说，总数可能太大。

测试样例

4 5 
88 200 
89 400 
97 300 
91 500

126900

提示

OUTPUT DETAILS:
In week 1, produce 200 units of yogurt and deliver all of it. In week 2, produce 700 units: deliver 400 units while storing 300 units. In week 3, deliver the 300 units that were stored. In week 4, produce and deliver 500 units.
输出详细信息：
在第一周，生产200单位的酸奶，并交付所有。在第2周，生产700台：交付400台，同时储存300台。在第3周，交付存储的300个单元。在第4周，生产并交付500台。

来源

USACO 2005 March Gold

解答

#include<iostream>

#define ll long long

using namespace std;

struct Node
{
    int cost;//价格
    int num;//数量
    int tag;//编号
} Days[10005];

int main()
{
    //freopen("E://test.txt", "r", stdin);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> Days[i].cost >> Days[i].num;
        Days[i].tag = i;
    }
    ll ans = Days[0].cost * Days[0].num;//第一天就是自己生产自己的

    int k = 0;
    for (int i = 1; i < n; i++)
    {
        ll xa = Days[i].cost * Days[i].num;//这周的东西自己生产
        ll xb = (Days[k].cost + m * (i - k)) * Days[i].num;//在之前最优周生产 加上存储到当前周的总费用

        if (xa > xb)
        {//本周生产的比较贵就使用以前生产的方案
            ans += xb;
        }
        else
        {//否则就使用本周的生产方案，并且将本周更新为最优周
            ans += xa;
            k = i;
        }
    }
    cout << ans << endl;
    return 0;
}