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$...
LuoguBZOJ分析先考虑一个 $O(n^2)$ 的暴力DP。设 $f[i]$ 表示 $1\sim i$ 的最大值。再设题目中的二次函数是 $F(i)$ ，$sum$ 是 $x$ 的前缀和，然后容易得到：代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstd...