YACS2021年7月乙组

T1:牛奶供应(三)

站在提前生产的角度来思考,为了缩小总成本,如果某天足够便宜就多生产一些牛奶。但这样的想法会遇到一个困难,也就是现在生产牛奶到底要生产多少箱,它是由之后的若干天决定的,而之后每天生产的成本和生产数量都不固定。

可以考虑逆向思维。

假设每天的牛奶都是当天生产出来的,但这样特别贵的日子就会很不划算。现在我们假设我们可以穿越时光回到过去,告诉前几天的我自己我要多生产多少箱从而满足我穿越来的那天所需要的牛奶需求。

一种做法是假设每天都要承担一个 \(i \times s\) 的保存费用,然后前面的最小历史单价就不需要承担保存费用

代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)

using std::cin;
using std::cout;
using ll = long long;

int main() {
    ll n, s;
    cin >> n >> s;
    
    ll ans = 0;
    ll mn = 1001001001; // 历史最小有效单价
    rep(i, n) {
        ll c, a;
        cin >> c >> a;
        c -= i*s;
        if (c < mn) mn = c;
        ans += (mn+i*s) * a;
        // std::cerr << ans << '\n';
    }
    
    cout << ans << '\n';
    
    return 0;
}

原文地址:http://www.cnblogs.com/Melville/p/16852311.html

发表评论

您的电子邮箱地址不会被公开。