*2100给定长度为 \(n\) 的数组 \(h, b\)，现在将这个数组划分为连续的若干段，每一段的价值为 \(h\) 最小的那个位置对应的 \(b\)，求出最大化的价值和。
\(1 \le n \le 3 \times 10^5\)，\(1 \le h_i \le n\)，\(|b_i| \le 10^9\)。
写出 DP 方程式，显然为：
这是一个经典的形式。注意到因为 \(w(j + 1, i)\) 取决于 \(h_{j + 1} \sim h_i\) 之间的最小值，所以 \(w\) 可以分为若干段，每一段都是相同的。
用一个单调栈来维护这样的段，段内记录最小值所在的点，以及 \(\max f\) 即可。
时间复杂度 \(O(n)\)。
*2400给定一张 \(n\) 个点的无向图，以及 \(q\) 个三元组 \((u, v, l)\)。一条边 \(e\) 被定义为「有用的」当且仅当存在一个三元组 \((u, v, l)\)，以及一条路径，满足：
数出图中的「有用的」边的数量。
\(2 \le n \le 600\)，\(0 \le m \le \frac{n(n - 1)}{2}\)，\(1 \le q \le \frac{n(n - 1)}{2}\)，\(1 \le w, l \le 10^9\)，图中没有重边和自环，三元组的 \(u, v\) 也互不相同。
首先求一遍 Folyd 得到两两点之间的最短路。
现在我们锁定一个点 \(v\)，关注所有与 \(v\) 之间相连的三元组 \((u_i, v, l_i)\)。
\(e = (a, b, w)\) 是有用的当且仅当存在一个三元组满足：
发现等号右边仅仅和 \(v\) 以及边本身有关，所以最小化左边即可。
具体的，对于 \((u_i, v, l_i)\)，将 \(d_{u_i} \gets -l_i\)，然后 \(O(n^2)\) 的 Dijkstra 进行扩展即可。
时间复杂度 \(O(n^3)\)。
Codeforces Round #709 (Div. 1, based on Technocup 2021 Final Round)
原文：https://www.cnblogs.com/syksykCCC/p/Technocup-2021-Final-Round.html