[USACO05MAR] 机器工厂(Yogurt Factory) 题解

思路分析

设前 $i-1$ 周生产并储存到第 $i-1$ 周的单台最低等效成本为 best，则储存到第 $i$ 周的单台成本为 best + S，与本周直接生产成本 $C_i$ 取较小值：best = min(best + S, C_i)，本周订单最小花费即为 best * Y_i。注意总花费最大可达 $10^4 \times 5000 \times 10^4 = 5 \times 10^{11}$，必须使用 long long。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long s;
    if (!(cin >> n >> s)) return 0;
    long long best = (1LL << 60);
    long long ans = 0;
    for (int i = 0; i < n; ++i)
    {
        long long c, y;
        cin >> c >> y;
        best = min(best + s, c);
        ans += best * y;
    }
    cout << ans << "\n";
    return 0;
}