假设只有一维，那么肯定是最奇数大的买，第偶数大的不买，以此类推。
但是现在有两维，如果只对一维做的话，另一维的顺序是不固定的，不好处理。
我们考虑发掘一点性质，假设对于两个物品 \((a_i,b_i),(a_j,b_j)\)，如果满足 \(a_i\leq a_j,b_i\geq a_j\)，则肯定不会 \(i\) 用 \(b\) 买 \(j\) 用 \(a\) 买，这样显然劣于 \(i\) 用 \(a\) 买 \(j\) 用 \(b\) 买。
因此，如果我们把点放到二维平面上，就会存在一条从左下到右上的折线，满足折线上方的选 \(a\)，折线下方的选 \(b\)。
这样我们就可以用 dp 来维护这个折线，设 \(f_{i,j}\) 表示折线在 \(i\) 处的取值为 \(j\) 的最小代价，转移容易用线段树维护矩阵乘法实现，时间复杂度 \(O(n\log n)\)。
标签：Price,QOJ,折线,一维,Combo,9222 From： https://www.cnblogs.com/275307894a/p/18384409