rt，写了一个线段树优化 DP，是这样的。

从 $1$ 到 $n$ 枚举每只怪物。在枚举到第 $i$ 只怪物时，$f_j$ 表示在 $k = j$ 时，前 $i - 1$ 只怪物中会选择战斗的数量。$g_i$ 表示要与第 $i$ 只怪战斗，最小的 $k$ 是多少。

转移有两个部分。

1. $g_i$ 通过二分 $f$ 得到，但需要证明 $\lfloor \frac{f_j}{j} \rfloor$ 单调不增。

2. 得到 $g_i$ 后，$f_{g_i}$ 到 $f_n$ 全部增加 $1$，但也需要证明同样的结论。

稍微感觉了一下，结论应该是对的，但求证明。