（私题）http://zhengruioi.com/contest/1485/problem/2734
容易想到 \(O(n^2)\) dp：设 \(dp_{i,j}\) 表示前 \(i\) 大的 \(x\) 与前 \(j\) 大的 \(y\) 所在的 pair 已被取走时的最小代价。转移时考虑第 \(i+1/j+1\) 大的 \(x/y\) 是否已经被取走，若是则不花费代价，否则花费对应代价即可。即钦定在第一次拿到某物品时花费代价。
但是这东西没什么优化空间啊！状态数卡的很死，且转移也不是很能优化。
考虑挖掘一些性质。
换个角度想，我们其实就是在钦定每个 pair 是选 \(x\) 还是 \(y\)，只不过由于选法的特殊性，有一些选择的方式是不合法的。考虑按某种顺序依次考虑每一个 pair 的选取决策，寻找一些关于合法性的约束：
-
若比当前 pair \(x\) 更大的 pair 还未选完，当前 pair 无法选择 \(x\)。
-
若比当前 pair \(y\) 更大的 pair 还未选完，当前 pair 无法选择 \(y\)。
-
若存在非偏序点对 \((a,b)\)，设 \(a_x<b_x,a_y>b_y\)，此时不能出现 \(a\) 选取 \(x\)，\(b\) 选取 \(y\) 的决策。
发现前两条其实是没什么用的，第三条则是有关当前局面合法性的充要条件。
考虑以 \(x\) 升序，设 \(dp_{i,j}\) 表示前 \(i\) 个 pair 选取后，选 \(x\) 的 pair 中最大的 \(y=j\) 的最小代价，此时若下一决策 \((x',y')\) 中的 \(y'>j\) 则可以该 pair 可以选取 \(y\) 或 \(x\)，否则只能选取 \(x\)。此时有转移方程：
\[\begin{cases}dp_{i+1,j}=dp_{i,j}+x,&y\le j\\dp_{i+1,y}=dp_{i,j}+x,&y> j\\dp_{i+1,j}=dp_{i,j}+y,&y>j\end{cases} \]我们发现该转移方程刚好是以 \(y\) 隔开的三段转移，用线段树维护即可，时间复杂度 \(O(n\log n)\)。
标签：8C,选取,当前,pair,代价,转移,dp,十连测 From： https://www.cnblogs.com/ydtz/p/17805665.html