2025.10.5-A
T1 misspelling
先刻画题目，\(T_u \le T_v,u<v\) 相当于 \(S_{[u,v]}\) 全部相等或 \(\forall k\in [i,p),S_i = S_k \text{且} S_i > S_p\)。
\(u>v\) 同理。
这样我们就从后向前转移 DP \(f_{i,j}\)，表示已经处理完 \([i+1,n]\)，其中 \(s_i = j\) 的方案数。
假设枚举一个 \(i' > i\) 进行转移，表示 \([i,i'-1]\) 全部相等，\(s_i' \neq s_i\)，如果存在 \(i \le u < i' \le v\)：
- 当 \(T_u \le T_v\) 时，\(\forall i' \in (u,v]\)，一定要有 \(j > j'\)
- 当 \(T_u > T_v\) 时，类似
也就是说，假设固定 \(i'\)，在 \(i\) 不断前移中，必然有一个位置让 \(i'\) 不能产生 \(j > j'\) 的贡献，也必然有一个位置让 \(i'\) 不能产生 \(j < j'\) 的贡献。
设 \(g_j\) 表示 \(f_{i+1} \sim f_n\) 的 \(j\) 的贡献。
现在枚举到 \(i\)，只考虑和 \(i\) 有关的贡献（\(i=u<v\)）：
- 若有 \(T_u \le T_v\)，\(\forall i' \in (u,v]\)，且仍产生 \(j < j'\)，删去该贡献，即 \(h_j\) 减去 \(\sum_{j < j'} f_{i',j'}\)。
- 若有 \(T_v \le T_u\)，同理。
更新完后更新 \(f_{i,j} = h_j + 1\)，\(1\) 表示全部相同的情况。
再更新 \(f_i\) 对 \(h\) 的贡献，即 \(h_j\) 加上 \(\sum_{j \neq j'} f_{i,j'}\)。
可以用链表维护仍然存在的贡献。
T2 ski 2
性质观察题，DP 解决。
结论一： 贪心的思考，一定是选高度最低的点建造酒店，如果1高度相同，就选建造设施最便宜的点，
结论二： 如果要提升发高度，最多只会提升至另一个点高度 \(+1\)。
结论三： 如果一个点建造了连接设施，那它就一定不会升高。
证明
若现在有 \(H_x < H_y\)，现在将 \(x\) 提升到 \(H_y+1\)，并且向 \(y\) 连边。
若 \(C_y \le C_x\)，则 \(x\) 连向 \(y\) 一定优，还可以将本来连向 \(x\) 的点改连向 \(y\)。
若 \(C_y > C_x\)，就可以放弃提升，将 \(y\) 连向 \(x\)，将本来连向 \(x\) 的点改连向 \(y\)，也一定更优。
所以，考虑 \(f_{i,j,k}\)，表示当前在高度 \(i\)，该高度上一共有 \(j\) 个可用的接口，有 \(k\) 个节点现在高度为 \(i\)，且准备抬升到 \(i+1\)。
- 可以新建一个链接设施，\(f_{i,j+1,k} = f_{i,j,k} + minc_i\)，其中 \(minc_i\) 指在高度 \(i\) 新建接口的最小花费。
- 可以向 \(i+1\) 转移，设高度 \(i\) 原本有 \(cnt_i\) 个节点，\(f_{i+1,j,max\{0,k+cnt_{i+1} - j\}} = f_{i,j,k} + K\cdot k \cdot (H_{i+1} - H_{i})\)。因为 结论三，所以新的 \(k\) 有 \(j\) 个节点一定不会再升高。
我们发现这样时间复杂度是 \(O(n^2\max H)\)。
考虑将 \(H\) 离散化，注意不止要加入 \(H_i\)，还有所有可能经过升高到达的高度。
时间复杂度 \(O(n^3)\)。