题目

---

分析

首先把宽度$l$按第一关键字从小到大排序，高度$h$按第二关键字从大到小排序，用一个栈把存在$h[x]\le h[y],l[x]\le l[y]$的情况消掉，然后一个显然的性质可以发现最优情况肯定是选择连续的一段，那么可以这样列出dp方程
d p [ i ] = min ⁡ { d p [ j ] + h [ j + 1 ] ∗ l [ i ] } dp[i]=\min\{dp[j]+h[j+1]*l[i]\} dp[i]=min{dp[j]+h[j+1]∗l[i]}
设$k(j<k)$优于$j$,那么$dp[j]+h[j+1]\ast l[i]\ge dp[k]+h[k+1]\ast l[i]$
那么化简可得$dp[j]-dp[k]\ge (h[k+1]-h[j+1])\ast l[i]$
因为若$h[k+1]\ge h[j+1]$，那么$l[k+1]>l[j+1]$也不符合消掉的情况，所以$h[k+1]<h[j+1]$
$$\frac{dp[j]-dp[k]}{h[k+1]-h[j+1]}\le l[i]$$
显然$l$是单调递增的，所以维护下凸壳，单调队列优化，时间复杂度$O(n)$

---

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
struct rec{int x,y;bool operator <(const rec &t)const{return x<t.x||(x==t.x&&y>t.y);}
}a[50001];
long long dp[50001]; int n,top,head,tail,q[50001];
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline double slope(int j,int k){return 1.0*(dp[k]-dp[j])/(a[j+1].y-a[k+1].y);}
signed main(){n=iut();for (rr int i=1;i<=n;++i) a[i]=(rec){iut(),iut()};sort(a+1,a+1+n);for (rr int i=1;i<=n;++i){while (top&&a[top].y<=a[i].y) --top;a[++top]=a[i];}n=top,head=1,tail=0,q[++tail]=0;for (rr int i=1;i<=n;++i){while (head<tail&&slope(q[head],q[head+1])<=a[i].x) ++head;dp[i]=dp[q[head]]+1ll*a[i].x*a[q[head]+1].y;while (head<tail&&slope(q[tail-1],q[tail])>=slope(q[tail],i)) --tail;q[++tail]=i;}return !printf("%lld",dp[n]);
}