Solution:

• 线性DP打牌\(+\)斜率优化
• 定义状态：\(dp[i]\)到了位置\(i\)最少花费
• 首先我们要发现，如果有一个小方块能被其他的大方块包围，其实可以忽略这个小方块，因为我们可以把他们俩捆绑，小方块的边长不会对求值造成贡献
• 然后我们可以按照宽从大到小排序，长从小到大（剔除了那种包含的情况），保证单调性

• 我们就可以列出递推式子：\(dp[i]=min(dp[j-1]+y[j]*x[i])\)

  注意是\(dp[j-1]\)(这里搞错了好久)

• 显然这个是满足决策单调性的嘛(主要是我不会证明)
• 然后我们就可玩弄这个式子，假定\(j<k\),那么\(y[j]>y[k]\)，\(dp[j-1]<dp[k-1]\)，且\(x[i]\)单调增
  \[dp[j-1]+y[j]*x[i]>dp[k-1]+y[k]*x[i]\]
  \[dp[j-1]-dp[k-1]>-(y[j]-y[k])*x[i]\]
  \[\frac{dp[j-1]-dp[k-1]}{y[j]-y[k]}>-x[i]\]

• 然后维护一个上凸包就ok了

Code:

//It is coded by Ning_Mew on 5.22#include
    
     #define LL long longusing namespace std;const int maxn=5e5+7;int n;struct Node{  LL x,y;}node[maxn];LL dp[maxn],large=-10000;int team[maxn],s=0,t=1;LL Min(LL a,LL b){return a
     
      b.y;return a.x>b.x;}double slope(int i,int j){  return 1.0*(dp[i-1]-dp[j-1])/(node[i].y-node[j].y);}int main(){  freopen("in.in","r",stdin);  scanf("%d",&n);  for(int i=1;i<=n;i++){scanf("%lld%lld",&node[i].x,&node[i].y);}  sort(node+1,node+n+1,cmp);  s=1;t=2;team[s]=1;  dp[1]=node[1].x*node[1].y;  large=node[1].x;    for(int i=2;i<=n;i++){    if(node[i].x<=large){dp[i]=dp[i-1];continue;}    large=max(large,node[i].x);    while((s+1
      
       -1.0*node[i].x)){      s++;    }        dp[i]=Min(node[i].x*node[i].y+dp[i-1],dp[ team[s]-1 ]+node[ team[s] ].y*node[i].x);        while((s+1
       
        slope(team[t-2],team[t-1]))){t--;}    team[t]=i;t++;  }  printf("%lld\n",dp[n]);  return 0;}