CodeforcesLuogu分析显然我们会在刷出一次升级机会后升级 $b_i\times p_i$ 最大的那个游戏，然后在接下来的时间内一直玩它。为了方便设 $M=\max\left\{b_i\times p_i\right\}$。考虑 DP。设 $dp_i$ 表示还剩 $i$ 秒且还没有得到过升级机会的最大期望收益，枚举每个游戏可以得到转移于是只要快速找到决策点改变的位置即可。一个想法是...
Luogu分析感觉对斜率优化那一套更熟练了呢 qwq首先有一个显然的性质：每一段左右端的贝壳大小一定相同，而且这一段的 $s_0$ 一定是左右端贝壳的大小。因为如果不是这样的话，我们显然可以把端点单独成一段，然后答案会变大。设 $dp_i$ 表示前 $i$ 个贝壳最多可以得到多少柠檬，$c_i$ 表示 $i$ 是第几个 $a_i$ 大小的柠檬，容易得到状态转移方程因为要求的是最大值，所以维护...
Luogu分析推完式子一遍码对了很舒服。设 $dp_i$ 表示前 $i$ 个士兵的最大战力，$sum_i$ 表示 $\sum_{j=1}^ix_i$，容易得到状态转移方程单调队列维护上凸壳即可，每次队头即为最优决策点。代码// =================================== // author: M_sea // website: http://m-sea-b...
Luogu分析斜率优化。我的式子可能比较长设 $dp_i$ 表示前 $i$ 个玩具的最小费用，$sum_i$ 表示 $\sum_{j=1}^ic_j$，容易得到状态转移方程把每个转移点看做一个点 $(x_j,y_j)$，那么我们相当于要找一个点，使得斜率为 $k_i$ 的经过它的直线的纵截距最小。可以发现可能满足条件的点一定在下凸壳上，因此我们只需要想办法维护下凸壳就好了。注意到 $k_i$...