【做题记录】Gym105244

· · 个人记录

记录

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. 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 数组后计算求和即可。