社区讨论

反悔贪心做法和 slope trick 是等价的

ccforrest
P4597序列 sequence参与者 4已保存回复 3

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mezrapk9
此快照首次捕获于
2025/08/31 21:58
6 个月前
此快照最后确认于
2025/11/04 08:53
4 个月前
查看原帖
有一个看起来完全不像是 slope trick 的题目，做法其实和本题是一致的。
CF865D ：给定股票价格序列，每天买一股、卖一股或者什么的都不做，要求最后一天结束时不持有股票，问最大利润。
这个问题等价于「求将价格序列调整为不增的序列的最小成本」。
CF865D 题解区只有反悔贪心做法，本题题解区的贪心基本都没讲反悔的事。但其实，本题的贪心也需要考虑反悔的问题，这也是需要插入两次的原因，也可能是很多读者困惑的原因。
至于这两个问题为什么等价，不是很好解释，这可能也是很多题解含糊其词的地方。
调整为不增之后，盈利一定为零，这是显然的。但是，对于一般的情况，这两个数值为什么相等，用自然语言说清楚，可能需要费一番功夫。
所以，本文补个简单的形式证明：（对序列边界处的处理略过，仅作为梗概）
将序列 {ai}\{a_i\} 调整为不增的最小成本为
min⁡b∑i∣ai−bi∣ s.t. bi≥bi+1.\min_{b}\sum_i|a_i-b_i|\text{ s.t. } b_i\ge b_{i+1}.
引入 Lagrange 乘子 λi\lambda_i 之后，问题等价于
min⁡bmax⁡λ≥0∑i∣ai−bi∣+λi(bi+1−bi).\min_b\max_{\lambda\ge0}\sum_i|a_i-b_i|+\lambda_i(b_{i+1}-b_i).
它进一步等价于对偶问题：
max⁡λ≥0min⁡b∑i∣bi−ai∣+bi(λi−λi−1).\max_{\lambda\ge0}\min_b\sum_i|b_i-a_i|+b_i(\lambda_{i}-\lambda_{i-1}).
当然，这里处理了一下后面的求和项，把所有和 bib_i 相关的项放在一块了。
而且，内层的最小化问题
min⁡bi∣bi−ai∣+bi(λi−λi−1)\min_{b_i}|b_i-a_i|+b_i(\lambda_i-\lambda_{i-1})
很好处理：要么 ∣λi−λi−1∣≤1|\lambda_{i}-\lambda_{i-1}|\le 1 时，最小值点就是 bi=aib_i=a_i，最小值为 ai(λi−λi−1)a_i(\lambda_i-\lambda_{i-1})；要么 ∣λi−λi−1∣>1|\lambda_{i}-\lambda_{i-1}|> 1 时，最小值为 −∞-\infty。
因此，最后，问题等价为
max⁡λ≥0, ∣λi−λi−1∣≤1ai(λi−λi−1).\max_{\lambda\ge 0,~|\lambda_{i}-\lambda_{i-1}|\le 1}a_i(\lambda_i-\lambda_{i-1}).
如果将 λi\lambda_i 理解为每日的持仓，那么 λi−λi−1\lambda_i-\lambda_{i-1} 就是当日的交易行为。对 λ\lambda 的限制只有两条：
  • 非负，亦即必须先买后卖；
  • 差值不能大于一，即单日交易的最大单位为一。
同时，式子隐含条件，即初值 λ0=0\lambda_0=0，这当然成立；问题对终值 λn=0\lambda_n=0 的限制并不必要，因为最后持仓为正只会白白损失利润。
这就说明，调整序列非增的问题，正好等价于股票交易的问题。
希望对大家理解有用。

回复

共 3 条回复，欢迎继续交流。

正在加载回复...