本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-08 23:48:46

记录

AG 还没做，C 没处理好方案输出，D 没判 $1\times 1$ 的边界，E 式子写错了，其他的没啥问题。

题解

A. New Adventures of the Wolf of Wall Street

待补。

B. Choosing a Vertex To Remove

树形换根 DP，设 $siz_u,sum_u,f_u$ 分别表示子树大小，子树权值和以及 $u$ 的所有子树贡献和，也即 $\sum_{v\in son_u}siz_v\times sum_v$，一遍 DFS 就能求出。

那么删掉根节点的答案即为 $f_{rt}$，然后进行换根 DP，计算 $v$ 答案时给 $f_v$ 加上其父亲的那颗子树，也即 $(n-siz_v)(tot-sum_v)$，其中 $tot$ 为所有节点的权值和。对所有的 $f_i$ 取最大值即可。

C. Space Expedition

二维 $01$ 背包，考虑像一维一样设 $f_{j,k}$ 表示两种容量分别为 $j,k$ 的最大代价，转移时也是倒序枚举 $j,k$，更新 $f_{j,k}=max(f_{j,k},f_{j-a_i,k-b_i}+v_i)$ 即可，最终答案为 $f_{A,B}$。

但是如果直接记 $p_{j,k}$ 表示 $f_{j,k}$ 最后使用的物品，直接输出答案的话，会出现重复的情况。因为最终的 $f_{j,k}$ 是考虑了所有元素的，可能同一个物品既会给 $f_{j,k}$ 更新，同时也会给 $f_{j-a_i,k-b_i}$ 更新，而对结果的影响是用倒序枚举消掉的，但方案就会炸掉。

所以改设 $f_{i,j,k}$ 表示前 $i$ 个物品给 $j,k$ 容量的最大价值，有 $f_{i,j,k}=\max(f_{i-1,j,k},f_{i-1,j-a_i,k-b_i}+v_i)$，这里用 $v_{i,j,k}$ 记录一下是从哪个转移来的，最后输出方案时从 $(n,A,B)$ 一直按照 $v_{i,j,k}$ 转即可，最后正序输出。

D. A Giraffe Travels and Munches

DP，设了两种状态，第二种要注意处理一下不用走，也就是 $n=m=1$ 的情况，不然会寄。

Sol.1

设 $f_{i,j}$ 表示最终停在 $(i,j)$ 的最大价值，用 $\frac{i+j-2}{k+1}$ 计算出走的次数以确定系数，若不能整除就到不了这格。然后从 $f_{i-k,j-1}$ 或 $f_{i-1,j-k}$ 转过来再加上这格的收益即可。最终答案为 $f_{n,m}$。

Sol.2

设 $f_{i,j}$ 表示走了 $i$ 次，其中 $j$ 次是向下 $k$，向右 $1$ 的最大价值，可以计算出最终的奇偶性。然后可以从 $f_{i-1,j}$ 或 $f_{i,j-1}$ 转移过来，最终枚举终点是 $(n,m)$ 的 $i,j$ 来更新答案即可。

E. Petya and Dice

发现只需要记录下有多少字符已经复原即可转移，设 $f_{i,j}$ 为操作 $i$ 次后 $j$ 个字符已复原的方案数，$f_{0,cnt}=1$。有以下分类转移:

• $f_{i,n}=\sum_{j=0}^{n-1}f_{i-1,j}$（全变对）
• $f_{i,0}=\sum_{j=0}^n f_{i-1,j}\times (25^n-[j=0])$（全变错）
• $f_{i,j}=f_{i,j}+24(n-j)f_{i-1,j}+(n-j+1)f_{i-1,j-1}+25(j+1)f_{i-1,j+1}$（修改）

滚动数组优化一下空间，少取模优化一下时间就能过。

F. Lottery

考虑把 $b_i$ 需要的次数求出来作为花费，$c_i$ 作为收益，就能转化为 $01$ 背包问题。设 $f_i$ 为变出 $i$ 需要的次数，初值 $f_1=0$，那么可以枚举 $j<i$，求出可用 $z$ 的范围为 $(\frac{j}{i-j+1},\frac j{i-j}]$，若有整数则可以转移 $f_i=\min(f_i,f_j+1)$。

这样就可以做 $01$ 背包了，但是复杂度 $O(nk)$ 达到 $10^9$，考虑减小 $k$，发现 $i$ 在 $10^3$ 之内的 $f_i$ 最大只有 $12$，那么全都变好至多也就 $1.2\times10^4$。所以把 $k$ 与所有 $f_{b_i}$ 的和取较小值即可，复杂度优化到 $10^7$ 级别。

G. Evolutionary Tree Weights

没讲，待补。

I. Sum of Path Lengths

把贡献拆到边上，那么点 $v$ 连到父亲的边的贡献为 $siz_v(n-siz_v)$，用树形 DP 处理出 $siz$ 数组后计算求和即可。