本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-01 22:43:49

记录

切了 ABCE，D 对着贪心调俩小时过不了，后来发现是 dp。老师要讲 FG，感觉 F 还行吧。

题解

A. Upload More RAM

答案显然为 $k(n-1)+1$，略过不表。

B. K-Sort

要求最终序列单调不降，考虑最终每个数至少需要加多少，也就是 $b_i=\max_{j=1}^{i-1}a_j-a_i$，维护目前的最大值即可求出。然后把大于 $0$ 的 $m$ 个 $b_i$ 拿出来升序排序。

发现每次操作都给所有还需要加的加上，这样操作比较集中，一定不劣。所以给后 $i$ 个一起加需要 $s_i-s_{i-1}$ 次，代价为 $m-i+2$，把所有的 $(s_i-s_{i-1})(m-i+2)$ 求和即为答案。

C. Basil's Garden

设 $f_i$ 表示 $a_i$ 变为 $0$ 需要的轮数，分讨一下 $a_i$ 和 $a_{i+1}$ 的大小关系，有边界 $f_n=a_n$，转移 $f_i=\max(f_{i+1}+1,a_i)$，对 $f_i$ 取最大值即可。

D. World is Mine

发现美味值相同的蛋糕可以分为同一组，可以转化为若干个数量 $b_m$。显然 Alice 只要选目前可选的美味值最低的就好了，因为这样后续可操作次数一定不劣。而 Bob 要考虑的事情就比较多了，需要把某一美味值的所有蛋糕在 Alice 选到之前全都选掉才能阻止 Alice 选。

所以转化为要在某一次数限制内消耗 $c_i$ 次来使 Alice 少选到一种，考虑反悔贪心，设 $cur$ 为目前剩余的次数，$res$ 为 Alice 选到的数量，再开个大根堆记录已经选过的 $c_i$。初始 $cur=0,res=0$，每次若 $c_i\le cur$ 就直接扔堆里，否则本次一定空了，$cur,res$ 均加上 $1$。同时若堆顶比 $c_i$ 大，可以用 $c_i$ 替换来省出一些次数加入 $cur$。最终 $res$ 就是答案。

E. Wonderful Tree!

叶子节点本身就合法，考虑从叶子节点向上 dp，也就是保证所有子树已经全部合法的情况下合并到根。初步理解是如果要让节点 $u$ 的子节点权值和增大，也就是给某个子节点加权值时，需要一直传递到某一叶子节点以保持子树的合法性。

但是写出来挂了，因为如果某一节点 $u$ 本来就合法，也就是 $a_u\ge \sum a_v$，那么这个点可以直接加权值而不用继续往下传递。所以设 $f_{u,i}$ 表示距离 $u$ 为 $i$ 的节点还能直接加多少权值。

则对于所有叶子节点 $x$ 均有 $f_{x,0}=+\infty$，合并到根时有 $f_{u,i}=\sum f_{v,i-1},f_{u,0}=a_u-\sum a_v$。同时每到一个节点使用剩余容量使其合法即可，可以发现这样在处理完整颗子树后根节点的权值不变，所以是正确的。

F. Interesting Problem

发现能用 $a_i$ 消除必须保证下标 $x=a_i$，也就是说需要在其前面删掉恰好 $b_i=i-a_i$ 个元素，所以 $i\ge a_i$ 且 $i$ 与 $a_i$ 同奇偶才有可能消除。然后考虑设 $f_{l,r}$ 为删掉 $[l,r]$ 需要在 $[1,l-1]$ 中操作的最少次数，然后区间 dp 枚举断点，还要考虑 $l$ 和 $r$ 为一组最后消除的情况。因此有：

• $f_{l,r}=\min(f_{l,r},f_{l+1,r-1}),f_{l+1,r-1}\le b_l$
• $f_{l,r}=\min_{k=l+1}^{r-2}\max(b_l,f_{l,k},f_{k+1,r}-\frac{k-l+1}2)$

然后再进行另一个 dp ，设 $g_i$ 表示前 $i$ 个数中的最大操作次数，当然可以转移 $g_i=g_{i-1}$。然后枚举上一轮断点 $j$，即 $g_i=\max_{j=0}^{i-1}g_j\ge f_{j+1,i}$，最后取 $g_n$ 即为答案。