但要记得那年海边的烟火，我们不拘一格 ，嘲笑过生活。

P10074 [GDKOI2024 普及组] 刷野 III

$\text{Tag : }$ 动态规划，斜率优化。

难点在于模型的构建。

首先，不难想到一个 $m=1$ 的做法，就是说你去钦定一个试错最大值 $\text{lim}$。对于每次打怪，无脑操作 $\text{lim}$ 次，如果还没到 $\text{lim}$ 次就死了，那就下一只，否则就跳过这一只。

容易发现，假设有 $x$ 只怪物的血量 $> \text{lim}$，也就是说，你在最优策略下，最多需要 $(x+1)\times \text{lim}$ 次操作，通过调整 $\text{lim}$ 的值从而得到 $m=1$ 的最优解。（且可以发现我们每次打死的那只怪的血量一定等于 $\text{lim}$）

考虑对于 $m>1$ 的情况进行扩展。先将原数组降序排序，假设我们最终打死的 $m$ 只怪物的编号分别是 $b_{1},b_2,...,b_m$（编号对应的是排完序之后的序列，且不妨设 $b_i<b_{i+1}$）。最优策略显然是我们对于打死的每只怪 $b_i$，对于 $(b_{i-1},b_i]$ 这中间的所有怪，使用 $m=1$ 的办法，将 $b_i$ 当作 $\text{lim}$，从而得到当前区间的最优解。然后把所有区间加起来就是答案。

由于不知道打死的编号序列，考虑 $\text{dp}$ 这个过程：

• 定义 $dp_{i,j}$ 表示 $b_j=i$ 时，当前杀死所有怪的最优策略所需的最少攻击数。
• 故有 $dp_{i,j}=\min_{k=1}^i{ dp_{k-1,j-1}+a_i\times (i-k+1)}$
• $dp_{n,m}$ 即是答案。
• 此时时间复杂度 $\mathcal{O}(n^2m)$。
• 注意到内部的转移式子是一个非常典型的斜率优化，可以直接套板子，将复杂度降为 $\mathcal{O}(n\times m)$。

P7747 [COCI 2011/2012 #3] TRAKA

$\text{Tag : }$ 动态规划，李超线段树。

其实并不是不会做的，但是一定要把式子写出来，不要懒。

方便计算答案的话，我们定义 $dp_i$ 表示开始装配第 $i$ 辆车的最早时间。为了方便我们后面的转移式，定义 $s_i=\sum_{j=1}^i t_j$。

故对于 $dp_i$ 有一个比较显然的转移：$dp_i=dp_{i-1}+\max_{j=1}^n {s_j\times f_{i-1}-s_{j-1}\times f_i}$。

于是我们有了一个比较 $\text{naive}$ 的 $\mathcal{O}(n\times m)$ 的做法。

很遗憾，没有办法直接通过。

注意到其实我们只关心如何快速求出后面 $\max$ 的这一坨。

可以稍微化简一下得到 $s_j\times f_{i-1}-s_{j-1}\times f_i=s_{j-1}\times(f_{i-1}-f_i)+t_j\times f_{i-1}$。

转移时 $i$ 已知，故可以把 $f_i,f_{i-1}$ 看作定值，令 $A=f_{i-1}-f_i,B=f_{i-1}$。

要想找到决策的 $j$，即找到 $s_{j-1}\times A+t_j\times B$ 的最大值。

稍微化一下，即快速求 $B\times (s_{j-1}\times \frac{A}{B}+t_j)$ 的最大值，注意到可以看作是 $n$ 条斜率为 $s_{j-1}$，截距为 $t_j$ 的线段，快速求出 $n$ 条线段在 $x=\frac{A}{B}$ 时的最大值是多少。

直接使用李超线段树即可，时间复杂度 $\mathcal{O}(m\log n)$。

$\text{Supplement}$

感觉有非常重要的两点：

• DP 式子写出来之后，再去看如何优化要明显的多，不要懒。
• 对于找最优策略的问题，可以钦定一个策略，然后看贡献是如何计算的，然后反推回去。