传送门

题意：已知未来 \(n\) 天的股价 \(c_i\)，每天可以买入一支或者卖出一支，求 \(n\) 天后利润总额最大是多少。

算法：模拟费用流。

【费用流模型】

把每一天抽象为一个结点：\(d_1\sim d_n\)。

\(S\rightarrow d_1\sim d_n\)，容量 \(1\) 费用 \(-c_i\)。

\(d_1\sim d_n\rightarrow T\)，容量 \(1\) 费用 \(c_i\)。

\(d_i\rightarrow d_{i+1}\)，容量 \(+\infty\) 费用 \(0\)。

求最大费用任意流，意思就是不限制流量但是要求费用最大。

对于任意流的模型，显然有这么一个思路：每次找费用最大的增广路，如果费用最大的增广路费用都非正，退出。

【模拟费用流】

直接费用流显然不行，传统的模拟费用流（整体考虑）不太好维护（因为 \(d_1\sim d_n\) 这一连串的边较难维护状态）。

在这里提出一种新的模型："增量-最大费用任意流模型"。（名字取自 command_block 的博客）

具体而言，每次增加一部分边/点，直到增加了所有边/点。增加后的最大费用任意流相较于增加前的最大费用任意流，只需要考虑三种东西的贡献：

1. 新的增广路。

2. 包含源点的正环。

3. 包含汇点的正环。

当然上面三种东西，都必须涉及新加入的边。