跳转至

P2517 [HAOI2010] 订货

题意

你需要管理冰棍的买卖。具体来说，有 \(n\) 天，第 \(i\) 天冰棍有 \(d_i\) 的需求量，订购单价为 \(p_i\)。你需要在一天开始时订购冰棍，并且必须满足当天的所有需求。冰箱大小为 \(S\)，每一根冰棍从第 \(i\) 天保存到第 \(i+1\) 天需要额外花费 \(m\) 的成本。如果冰棍当天就卖出了，则不需要支付保存成本。

问如何决策每天买入冰棍的数量，才能使总成本最小？

题解

费用流做法比较显然，这里讲一种单调栈维护反悔贪心的线性做法。

假设第 \(i\) 天购买了 \(x_i\) 根冰棍。保存的费用可以表示为

\[ m\sum_{i=1}^n{\left(\sum_{j\le i}{x_j}-\sum_{j\le i}d_i\right)} \]

化简：

\[ \sum_{i=1}^n{m(n-i+1)(x_i-d_i)} \]

\(d_i\) 是常数，容易计算，暂不考虑。再给 \(x\) 加入订购单价 \(p_i\) 的贡献：

\[ \sum_{i=1}^n{\big(m(n-i+1)+p_i\big)x_i} \]

记 \(k_i=m(n-i+1)+p_i\)；问题即转化为，在满足每天需求，并且不能超过冰箱容量的情况下，最小化

\[ \sum_{i=1}^n{k_ix_i} \]

先考虑如何满足每天的需求。我们构造 \(\forall i,\ x_i=d_i\)，这是一组可行解，但不一定最优。我们通过将一些冰棍的购买提前（把后面的 \(x_i\) 向前调整）实现最优化，同时能保证每天的需求被满足。

考虑贪心，我们从第 \(n\) 天枚举到第 \(1\) 天，假设当前已经得到了一个后缀 \([i+1,n]\) 的最优解。对于第 \(i\) 天，我们可以多买一些冰棍，替换掉 \([i+1,n]\) 中一些更劣（\(k_j\ge k_i\)）的冰棍。

我们可以使用一个数据结构维护后缀中所有 \(x_j\ne 0\) 的 \(j\) 和对应的 \(k_j\)，每次优先替换 \(k_j\) 最大的冰棍。

那我们如何处理冰箱容量的约束呢？首先，\(\forall i,\ x_i\le p_i+S\)，否则当天的冰棍就已经不能装进冰箱了。我们能够证明，只需要满足这个条件，按照我们的贪心顺序求出的方案一定合法。

考虑 \([i+1,n]\) 中第一个 \(x_j\ne 0\) 的 \(j\)，和第一个 \(x_t=p_t+S\) 的 \(t\)（冰箱满了，\(>t\) 的部分都无效），\(k_j\) 一定是闭区间 \([j,t]\) 中所有 \(x\ne 0\) 的位置中 \(k\) 最大的一个。否则将 \(k\) 更大（更劣）的那个位置上的冰棍都放到 \(j\) 这天购买，一定更优。

同理，我们可以证明闭区间 \([i+1,t]\) 中所有 \(x\ne 0\) 的位置，它们的 \(k\) 值单调递减。因此，第 \(i\) 天多出来的冰箱容量一定优先分配给 \([i+1,t]\) 中最靠左的 \(x\ne 0\) 的位置。

对于 \(x_j=0\) 的位置，它们不产生冰棍，只消耗冰棍，因此对库存是有利的，瓶颈不在于它们。

对于最左边的 \(x_j\ne 0\) 的 \(j\)，若 \(k_i<k_j\)，我们尝试将 \(i\) 的冰棍分配给它。考虑两种情况：

  1. 如果 \(i\) 的剩余容量 \(p_i+S-x_i\ge x_j\)，\(i\) 可以把第 \(j\) 天的冰棍全都包下来，\(x_i'\leftarrow x_i+x_j\)，\(x_j'\leftarrow 0\)；
  2. 此时第 \(i\) 天冰箱的剩余容量不会超过原本第 \(j\) 天冰箱的剩余容量，因为 \(p_i+S-x_i-x_j\le p_j+S-x_j\)（\(p_i-x_i\le 0\le p_j\)）；
  3. 因此本次操作之后，即使第 \(i\) 天装满冰箱，等到第 \(j\) 天结束时冰箱也不会超载。
  4. 因为 \(x_j=0\)，所以将 \(j\) 弹出数据结构，继续考虑下一个 \(x_j\ne 0\) 的 \(j\)。
  5. 如果 \(i\) 的剩余容量 \(p_i+S-x_i< x_j\)，\(j\) 会把 \(i\) 的剩余容量消耗完。根据上面的论述，冰箱仍然不会超载。

分配冰棍不要求 \(x_j\ne p_j+S\)，这种情况属于第 \(2\) 种情况，\(j\) 会把 \(i\) 的库存消耗完，不会增大 \(j\) 这天的冰箱负载，以后也一定不会发生。

因此，我们只需要使用一个单调栈维护第一个 \(x_j\ne 0\) 的位置即可。

AC 代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
using namespace std;
const int N = 100;

int n, m, s, ans;
int d[N], p[N];

int k[N], x[N];

int sta[N], top;

int main() {

    cin >> n >> m >> s;
    for(int i = 1; i <= n; i++) cin >> d[i];
    for(int i = 1; i <= n; i++) cin >> p[i];

    for(int i = 1; i <= n; i++) {
        k[i] = (n - i + 1) * m + p[i];
    }
    for(int i = 1; i <= n; i++) {
        x[i] = d[i];
        ans -= m * (n - i + 1) * d[i];
    }

    top = 0;
    for(int i = n; i >= 1; i--) {
        while(x[i] - d[i] < s && top && k[i] <= k[sta[top]]) {
            int tmp = min(s + d[i] - x[i], x[sta[top]]);
            x[sta[top]] -= tmp;
            x[i] += tmp;
            if(!x[sta[top]]) --top;
        }
        sta[++top] = i;
    }

    for(int i = 1; i <= n; i++) {
        ans += k[i] * x[i];
    }

    cout << ans << endl;

    return 0;
}