题目描述
翻译的不是很好，所以我简化一下题面。
给定 $n$ 个矩阵的宽 $w$ 和高 $h$，每次选一个矩阵集合，代价为集合中的 $\max{\{w\}}\times \max{\{h\}}$。
任意两次之间没有重复的矩阵，求取完所有矩阵的最小代价。
定义
矩阵的两个参数为 $w, h$，分别对应下图中的宽和高。
函数 $\operatorname{slope}(i, j)$ 表示 $(x_i, y_i)$ 与 $(x_j, y_j)$ 构成的直线的斜率，$x, y$ 的含义在下面会说。
分析
注意到对于两个矩阵 $i, j$，如果 $w_i\leq w_j$ 并且 $h_i\leq h_j$，那么 $i$ 和 $j$ 一定可以放到一组，$i$ 对答案没有贡献，不用考虑，可以直接删去。
比如下图当中的 $1$ 和 $2$. 矩阵 $2$ 能完全被 $1$ 包含，所以 $2$ 没有贡献，可以删去。
于是考虑先删除所有 $i$ 这样的矩阵。
具体做法就是：按照 $h$ 为第一关键字，$w$ 为第二关键字从大到小排序，之后双指针扫一遍即可。
//a已经降序排序
int t = 0;
for(int i = 1; i <= n; i++) {
if(a[i].w > a[t].w) a[++t] = a[i];
}
如上图，剩下的只有 $1, 3$ 号矩阵。
删完之后剩下的就是一个，$h$ 严格单调递减，$w$ 严格单调递增的序列。考虑 $DP$ 解决。
DP
设 $f_i$ 为新序列中，取走前 $i$ 个矩阵的最小花费，$w$ 为宽（单调递增），$h$ 为高（单调递减），那么有转移方程：
f_i=\min_{j=0}^{i}{\{f_{j}+w_ih_{j+1}\}}
$$
相当于，把 $j+1$ 到 $i$ 这一段合为一组取走。由于单调性，所以这一组的 $\max{\{w\}}=w_i$，$\max{\{h\}}=h_{j+1}$.
复杂度 $\mathcal{O}(n^2)$。这显然可以斜率优化。
斜率优化
我们目前优化的目的，是尽快地找到 $f_i$ 到底是由哪个 $j$ 转移过来的，也就是尽快找到最小化 $f_i$ 的继承状态。
为了表示方便，设 $j$ 为能使 $f_i$ 最小化的继承状态，所以有：
f_i=f_{j}+w_ih_{j+1}
$$
考虑一次函数斜截式 $y=kx+b$ 或 $b=y-kx$，将状态转移方程变换为这个形式：
f_{j}=-w_ih_{j+1}+f_i
$$
其中变量 $x, y$ 与 $j$ 有关，$b, k$ 与 $j$ 无关。且要求 $x$ 随 $j$ 单调递增，$b$ 中包含 $f_i$（斜率优化基本操作）。
所以可以构造出直线方程为：
\left\{
\begin{array}{lr}
y = f_j\\
k = w_i\\
x = -h_{j+1}\\
b = f_i
\end{array}
\right.
$$
我们把 $(x, y)$ 看成平面直角坐标系上的点。那么现在 $(x_j, y_j)$ 的意义就是：直线 $y=kx+b$ 上的一个点。
又因为我们的目的是最小化 $f_i$，在上面的表示当中，$f_i$ 只与直线的截距 $b$ 有关。所以显然地，问题转化为：如何选取 $j$ ，才能使得过点 $(x_j, y_j)$ 的直线的截距 $b$ 最小。
显然，对于一个斜率 $k$ 来说，最优解 $j$ 就是从左往右枚举到的第一个 $\operatorname{slope}(j, j+1)>k$ 的点。（其中 $\operatorname{slope}$ 的定义在上面有说过）
再考虑单调性： $x$ 随 $j$ 单调递增，$k$ 随 $i$ 单调递增，要使截距 $b=f_i$ 最小。
显然，所有的最优决策点 $j$ 都在下凸包上，也就是上图中的折线。
所以单调队列维护下凸包即可：
设单调队列（递增）为 $q$，队首为 $head$，队尾为 $tail$，当前要转移 $i$ 号点，那么具体步骤：
- 当 $\operatorname{slope}(q_{head}, q_{head+1})\leq w_i=k_i$ 时，$head$++，（保证最优解）
- 此时的 $q_{head}$ 就是最优转移点，根据它和转移方程计算出 $f_i$，
- 当 $\operatorname{slope}(q_{tail-1}, q_{tail})\geq\operatorname{slope}(q_{tail}, i)$ 时，$tail$–，（维护下凸包）
- 在队尾插入 $i$.
代码
#include <bits/stdc++.h>
#define X(i) (-a[i+1].h)
#define Y(i) (f[i])
#define int long long
using namespace std;
const int MAXN = 5e4 + 10;
int n;
struct Node{
int w, h;
} a[MAXN];
int f[MAXN];
bool cmp(Node i, Node j) {
return (i.h > j.h) || (i.h == j.h && i.w > j.w);
}
double slope(int i, int j) {
return (Y(j) - Y(i)) / (double)(X(j) - X(i));
}
int head, tail, q[MAXN];
signed main() {
scanf("%lld", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld%lld", &a[i].w, &a[i].h);
}
sort(a + 1, a + n + 1, cmp);
int t = 0;
for(int i = 1; i <= n; i++) {
if(a[i].w > a[t].w) a[++t] = a[i];
}
n = t;
head = tail = 1;
for(int i = 1; i <= n; i++) {
while(head < tail && slope(q[head], q[head + 1]) <= a[i].w) {
head++;
}
int j = q[head]; f[i] = f[j] + a[i].w * a[j + 1].h;
while(head < tail && slope(q[tail - 1], q[tail]) >= slope(q[tail], i)) {
tail--;
}
q[++tail] = i;
}
cout << f[n] << endl;
return 0;
}