题意
给定数列 \(A, B, C\)，每次操作，你可以花 \(1\) 的代价将 \(A_i\) 或 \(B_i\) 或 \(C_i\) 增加 \(1\)。
求使得三个数列每个元素排名相同的最小代价。
\(n \le 500\)
Sol
很厉害的题目。
首先注意到这个最优方案只和前缀最大值有关，考虑设 \(f_{i, j, k}\) 表示当前状态枚举到了三个数列的排名分别是 \(i, j, k\) 的最小代价。
没法转移？
枚举每步走多少，考虑计算转移带来的贡献。
若一个三元组第一次被偏序，则该三元组一定会操作到该状态。
这个结论很好理解，转移到第一次偏序的位置一定不劣。
考虑 \(A_x \le i\) 的三元组，注意到若三元组 \((A_x, B_x, C_x)\) 已经被当前状态偏序了，则该三元组一定被当前或之前的状态算到。
而对于未偏序的三元组，则会随第一维状态，转移到 \(f_{i + l, j, k}\)。
另两维的转移同理。
当前复杂度： \(O(n ^ 4)\)。
考虑优化，注意到该问题可以转化为三维空间路径，对于一步：\(x \to x + l\)，和走 \(l\) 步 \(x \to x + 1 \to x + 2 \to ... \to x + l\) 是等价的。
因此直接将枚举 \(l\) 去掉，暴力转移即可。
复杂度：\(O(n ^ 3)\)。
标签：偏序,状态,数列,省选,rose,YC281A,三元组,枚举,转移 From： https://www.cnblogs.com/cxqghzj/p/18177711