本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-28 22:53:23

记录

赛时 A 假 B 不会，C 调过了，D 也假，E 没看，比较寄。

题解

A. P7667 [JOI2018] Art Exhibition

发现由于要价值和减去尺寸极差最大，且价值均为正，所以若按尺寸排序，最优解一定是一段连续区间。

考虑预处理价值的前缀和 $s$，设取的区间左右端点为 $x,y$。拆式子，得到 $S-(A_{max}-A{min})=s_y-s_{x-1}-(A_y-A_x)=(s_y-A_y)+(A_x-s_{x-1})$，枚举其中一个括号，另一个维护前后缀最大值即可。

B. P7668 [JOI2018] Dango Maker

如果均不冲突，暴力求个数即可。需要考虑的是有冲突时如何计算，通过举例发现任意两个冲突的串一定是一横一竖，同时 G 在同一条左下-右上对角线上相邻或相同。

所以对于每一条对角线分别考虑，由于两条对角线之间没有相互影响，相互独立。这时设 $f_{i,0/1/2}$ 表示前 $i$ 个中第 $i$ 个不选/竖选/横选的代最大个数，只要保证上一个不选或上一个与当前的串方向不同即可。

C. P6304 [eJOI2018] 山

考虑设 $f_{i,j}$ 表示前 $i$ 座山上选 $j$ 个的最小代价，发现难以转移，所以加一维 $k=0/1$ 表示第 $i$ 个本身是否被选，同时若 $i$ 被选保证 $a_{i-1}<a_i$ 的最小代价，这样能防止重复计算代价。

所以 $f_{i,0}$ 从 $f_{i-1}$ 直接转过来，若选 $i-1$ 还要保证把 $a_i$ 减至小于 $a_{i-1}$。$f_{i,1}$ 从 $f_{i-2}$，转过来，要把 $a_{i-1}$ 减至小于 $a_i$，若同时也选 $i-2$ 也要保证小于 $a_{i-2}$。

D. P5089 [eJOI2018] 元素周期表

考虑建模成一个二分图，左部点表示行，右部点表示列，每两个点之间的连接情况相当于原图中的一个格是否被填。发现最终要求转化为完全图，同时每个连通块内一定能转化成局部完全图。所以把原有的点作为边，答案等于连通块个数 $-1$。

E. P7669 [JOI2018] Commuter Pass

发现最终答案一定是一段非 $0$，一段 $0$ 再一段非 $0$，军可能为空。因为如果有多段 $0$ 却不连续，那么前一段的结尾 $X$ 和后一段的开头 $Y$ 一定都在 $S$ 到 $T$ 的最短路上，所以一定可以用中间的 $0$ 补起来，一定较优。

但是暴力枚举 $0$ 的两端 $A,B$ 会产生 $O(n^2)$ 的时间复杂度，寄。考虑优化，把 $S$ 到 $T$ 的最短路树建出来，一定是以 $S$ 为源点的 DAG。在上面跑拓扑排序以求出 $U$ 到每个点的最短距离，初始化为原来的最短距离，对于每个 $v$ 更新 $dis_v=\min(dis_v,dis_u)$，也就是走了一条 $0$。最后用 $dis_i+dis_{i,V}$ 更新即可。由于可能以最短路的反向经过最短路，还要建反图再跑一遍。