YACS2021年7月乙组

5月前 0 3

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

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。