Travel with candy

attention -> 0

题目链接： HDU 2015 Travel with candy 。

题目描述：

有 $n+1$ 个城市，编号 $0\sim n$ 。第 $i$ 个城市距离 $0$ 号城市 $a_i$ ($a_{i-1}<a_i<a_{i-1}+C$) 。你在第 $i$ 个城市可以以 $by_i$ 的价格买糖，或者以 $sl_i$ 的价格卖糖（ $by_i>sl_i$ ）。

你初始时在 $0$ 城市，你想要到 $n$ 城市。你每往右走一单位距离要吃一颗糖。

你最多一次拥有 $C$ 颗糖。

求你这次旅行的最小花费（可能为负数，原因是你可以通过买卖赚钱）。

$n\le 2\times 10^5,C\le 10^6,a_i\le 10^9,0\le sl_i<by_i\le 10^6$ 。

我们有一个显然的暴力 DP ： $f_{i,j}$ 表示到 $i$ ，拥有 $j$ 颗糖的最小花费。

这个 DP 显然不是特别可优化的。然后我们就注意到如下性质：

$$\forall i\in[0,n],f_{i,j+1}-f_{i,j}\ge f_{i,j}-f_{i,j-1}$$

即，你在城市 $i$ 每多拥有一颗糖，代价会变高。

考虑利用这一点优化 DP 。

我们先维护一个“可以买”的单调队列，队首表示最小的单价，队尾表示最大单价。初始时为 $C$ 个 $\infty$ 。

设 $A$ 表示到城市 $i$ 为止的答案，则对于城市 $i$ ，有三种决策：

Case #1: 买

此时我们应该用 $by_i$ 去更新队尾。具体的，对于所有 $x>by_i$ 的队尾 $x$ ，应该全部弹出。然后补充 $by_i$ 直到队列有 $C$ 个元素。这个操作显然不影响 $A$ 。

Case #2: 卖/吃

此时有些复杂。理论上，我卖的时候，应该将队首所有 $x<sl_i$ 的元素 $x$ 全部弹出，然后 $A-(sl_i-x)\to A$ 。然而这并不一定最优秀：因为“吃”相当于白白浪费一颗糖，所以如果直接在“卖”时全部弹出，则“吃”的时候可能会以更劣的价格消耗。此时之前的性质作用就来了：因为我赚糖的代价会越来越高，所以一个后面的糖被吃肯定不优，于是我必须保证“吃”队首的糖。但是我“卖”的时候并不知道这些糖会不会在以后被吃掉，于是我们就要做一个反悔操作。

具体的，我把 $sl_i$ 当作一个“糖”放入队首，我卖了多少个就放多少个。这样以后在我“吃”的时候，我就会再消耗 $sl_i$ 的代价弹出 $sl_i$ 。而我之前“卖”的时候已经获得了 $sl_i-x$ 的收益。于是，我就成功的里 $x$ 的代价进行了一个“吃”操作。

PS: 当“吃”操作进行后，队列元素可能会不满 $C$ 个，这时候补 $\infty$ 就行。

总结

总的来说，对于 $i$ ，有三种决策：

1. 将所有 $x>by_i$ 的队尾弹出，并在队尾补上 $by_i$ 。
2. 将所有 $x<sl_i$ 的队首弹出，令 $A-(sl_i-x)\to A$ ，弹出队首，并在队首补上 $sl_i$ 。
3. 将 $a_{i+1}-a_i$ 个糖全部从队首弹出，令 $A+x\to A$ ，并在队尾补上 $\infty$ 。

于是这一题就完了。

PS: 这个队列直接维护复杂度有 $\mathcal{O}(nC)$ ，由于队列中涉及大量相同元素的操作，于是我们可以将队列改为维护 $(A,B)$ 的二元组，表示值为 $A$ 且数量为 $B$ 。