CF455E Function
Codeforces 分析 我们可以把题目中的过程看成二维网格上的游走，即每步可以向下或向右下走，代价为该列的权值，求从第一行走到 $(x, y)$ 的最短路。 注意到这样的最短路一定是先往下走若干步，然后往右下走到终点。因此设 $s$ 为 $a$ 的前缀和，那么从 $(1, i)$ 走到 $(x, y)$ 的最短路为 $s_y - s_i + a_i(x - y + i)$。我们要对每个询...
Codeforces 分析 我们可以把题目中的过程看成二维网格上的游走，即每步可以向下或向右下走，代价为该列的权值，求从第一行走到 $(x, y)$ 的最短路。 注意到这样的最短路一定是先往下走若干步，然后往右下走到终点。因此设 $s$ 为 $a$ 的前缀和，那么从 $(1, i)$ 走到 $(x, y)$ 的最短路为 $s_y - s_i + a_i(x - y + i)$。我们要对每个询...
Codeforces Luogu 分析 显然我们会在刷出一次升级机会后升级 $b_i\times p_i$ 最大的那个游戏，然后在接下来的时间内一直玩它。为了方便设 $M=\max\left\{b_i\times p_i\right\}$。 考虑 DP。设 $dp_i$ 表示还剩 $i$ 秒且还没有得到过升级机会的最大期望收益，枚举每个游戏可以得到转移 于是只要快速找到决策点改变的位置即可...
Luogu 分析 首先有一个显然的性质：每一段左右端的贝壳大小一定相同，而且这一段的 $s_0$ 一定是左右端贝壳的大小。因为如果不是这样的话，我们显然可以把端点单独成一段，然后答案会变大。 设 $dp_i$ 表示前 $i$ 个贝壳最多可以得到多少柠檬，$c_i$ 表示 $i$ 是第几个 $a_i$ 大小的柠檬，容易得到状态转移方程 因为要求的是最大值，所以维护上凸壳；因为 $x_i$ 单...