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$ 单...