上海计算机学会2021年7月月赛C++乙组T1牛奶供应（三）

为了使小爱在满足所有订单的情况下总成本最小化，我们需要逐天决策是否重新开始生产和储存牛奶以降低整体成本。通过比较当前材料费与之前所有可能重新开始生产的最低材料费之和加上相应的存储费用，选择最优策略来确定每日产量和储存情况。
解答思路
问题分析：每天可以选择继续储存上一天剩余牛奶并支付仓储费或重新开始生产和支付材料费。目标是最小化总成本。
核心思想：逐天决定是否重新开始生产和储存牛奶以降低整体成本。
算法选择：遍历每一天计算累积最少成本，并记录并更新当前最优决策点。
复杂度分析：时间复杂度为O(n)，适用于处理最大约一百万的数据量。
解决代码
cpp #include <iostream> using namespace std; int main() { int n, s; long long ans = 0; cin >> n >> s; for (int i = 1; i <= n; ++i) { int c, a; cin >> c >> a; if (i == 1) { int d = c; } else { d += s; if (d > c) { d = c; } } ans += d * a; } cout << ans << endl; return 0; }
总结
通过逐天评估当前材料费与之前所有可能重新开始生产的最低材料费之和加上相应的存储费用，并选择最优策略来确定每日产量和储存情况的方法可以有效地解决问题，并且确保在合理的时间内完成计算任务。

题目描述

小爱经营一家牧场专门生产牛奶，在未来 n 天内每天都将会有相应的订单需求。在第 i 天时（i=1,2,…,n），牧场必须向市场供应 ai 箱牛奶以满足当天的需求。生产牛奶的成本来源主要包括两个方面：

• 主要涉及材料费用。由于原料价格每天都在变动，在第i天生产一箱牛奶时, 每生产一箱牛奶需投入ci元的材料费用。
• 另一方面涉及存储费用. 当原材料成本上涨时, 可以通过提前制作一批牛奶存放在冷库中进行储存. 但需承担仓储费用储存一箱奶一天的费用是s元。

每天的产能无限制，在任何一天都可以生产出任意数量的牛奶；冷库存储容量同样无限制，并且假定奶畜可存贮时间无限长。

希望了解具体方式：以满足这些订单的需求，小爱应如何合理安排每日生产量，并采取哪些存储策略才能将总成本降至最低水平？

输入格式

第一行：两个整数 n 和 s。
第二行到第 n+1 行：第 i+1 行有两个整数 ci​ 和 ai​。

输出格式

单个整数：表示为了满足所有订单的最小总成本。

数据范围

• 1≤s≤100,000；
• 1≤ci​≤100,000；
• 1≤ai​≤100,000；
• 对于 30% 的数据，1≤n≤20；
• 对于 60% 的数据，1≤n≤5,000；
• 对于 100% 的数据，1≤n≤1,000,000。

样例数据

输入:
每日产量为10箱
每箱售价为100元
每箱存储费为5元
第三天安排生产297台设备
输出:
总金额为2859.64美元
说明:
第一工作日完成组装任务168台设备（单价为每台9.44美元）
第二工作日未安排生产任务（剩余库存产生存储费用合计6.37美元）
第三工作日完成组装任务479台设备（单价为每台6.23美元）

解析：每天计算当天的总成本（包括当天的生产成本和仓储费用），然后将其与当天的生产成本进行比较，并选择较低的那个值。

详见代码：

 #include <bits/stdc++.h>

    
 using namespace std;
    
 int a[1000005];
    
 int c[1000005];
    
  
    
 int main() {
    
     int n, s;
    
     long long ans = 0;
    
     cin >> n >> s;
    
  
    
     for (int i = 1; i <= n; i++) {
    
     scanf("%d %d", &c[i], &a[i]);
    
     }
    
     int d;//当前最低生产成本
    
     for (int i = 1; i <= n; i++) {
    
     if (i == 1) {//第一天
    
         d = c[i];//生产成本
    
     } else {
    
         d += s;//增加仓储成本
    
         if (d > c[i]) {//如果当天生产成本低于之前的最低生产成本
    
             d = c[i];//当天生产
    
         }
    
     }
    
     ans += d * a[i];//单位成本*数量
    
     }
    
     cout << ans << endl;
    
     return 0;
    
 }