SS241009C. 蛋糕（cake）

题意

你有 \(n\) 个数字，有两种操作。

1. 删除最左边的数字，代价为数字大小。（吃左边）
2. 令 \(>0\) 的所有数字大小减 \(1\)，代价为 \(>0\) 的最大的数字的初始值。（吃底下）

求删完所有数字的最小代价。

思路

据搜索引擎，凹包不具有斜率单调性质，因此题解说的凹包应为凸包。没听说过凹包，OI 不考吧

凸包好抽象，但是凹包更抽象

以下说的截距均指函数和 \(y\) 轴交点。

容易想到 DP。设 \(f_{i,j}\) 表示已经删完 \(a_{1 \sim i-1}\)，做了 \(j\) 次吃底下，的最小贡献。

假设删除一个空的数字代价为 \(0\)，答案就是已经删完 \(n\) 个数字，做完任意次吃底下的最小代价，即 \(f_{n+1,x}\)。

设 \(b\) 为后缀最大值数组。有转移方程：

• \(f_{i,j} + \max(a_i -j,0) \to f_{i+1,j}\)
• \(f_{i,j} + b_i \to f_{i,j+1}\)

暴力做是 \(O(n^2)\) 的。

根本不能容易感觉这个函数具有凸性。

或许突破口不在感觉有凸性，可能是我们看到答案并不关心 \(j\) 这一维，因此考虑吧 \(j\) 这一维作为自变量，研究函数 \(f_i(j)\) 的性质。

\(f_i(j)\) 由 \(f_{i-1}(j)\) 先做若干次吃底部，再做一次吃左边得到。

也就是先加若干次 \(b_i\)，再加一个 \(\max(a_i-j,0)\)。

有 \(f_1(0)=0\)，先做吃底部，\(j=\) 多少就要吃多少次，因此 \(f_1(j)\gets f_1(0)+(h(j)=b_1j)\)。

这个 \(h(j)\) 长成一条斜率为 \(b_1\) 的斜线。

然后做吃左边，\(f_1(j) \gets f_1(j) + (g(j)=\max(a_1-j,0))\)。

这个 \(g(j)\) 长成前一段是斜率为 \(-1\)，截距为 \(a_1\) 的直线，后一段恒为 \(0\)。

那么 \(h(j)+g(j)\) 长成前一段是两条直线相加，斜率相加，是 \(b_1-1\)，截距是 \(a_1\)，后一段就是 \(h(j)\)。且两段是连接的。

考虑 \(f_2(j)\) 长什么样子。

先做若干次吃底部操作，即 \(f'=f_2(0)+(h_2(j)=b_2j)\)。

截距是 \(\sum a_1 \sim a_{2-1}\)，斜率是 \(b_2\)。

已知后缀最大值数组 \(b_2 \le b_1\)。

再做一次吃左边操作。可以在我们的 \(f_1(j)\) 或者 \(f'\) 上面做。即取 \(f''=\min(f_1,f')\)。在 \(f''\) 上面加上 \(g_2(j)=\min(a_2-j,0)\)。

\(f''\) 长成一个下凸壳和一个直线取 \(\min\)，截距一样，下凸壳斜率由 \(b_1-1 \sim b_1\)，直线斜率 \(b_2\)，相当于对斜率取 \(\min\)，仍然是一个凸壳。

\(f_2(j)=f''+g_2(j)\)，长成截距是 \(\sum a_1 \sim a_2\)，斜率就是两个函数相加。

然后这么搞，维护出 \(f_{n+1}\)，斜率为 \(0\) 的拐点就是答案了。

就是维护一个斜率递增的下凸壳。吃底下就是所有斜率对 \(b_i\) 取 \(\min\)，把后面的大斜率 pop 掉换成 \(b_i\) 就行。吃左边就是截距加上 \(a_i\)，\(j < a_i\) 的斜率 \(-1\)，应该可以打 tag 做。

由上面的介绍可以证明我们的 \(j\) 可以只关心离散化的 \(a_i\)。

时间复杂度 \(O(n \log n)\)。

code

待订正