Solution
发现对于一块土地 \(x\) 和 \(y\) ,如果 \(l_y\geq l_x,h_y\geq h_x\) ,那么把 \(x\) 和 \(y\) 合在一组对答案是不会更劣的。
将土地按照长度和宽度排序,维护一个栈,将有必要存在的土地留下。
在最优决策下,每一组土地都是连续的。因为如果有 \(x,y,z\) 三块连续土地,并且 \(l_x<l_y<l_z,h_x>h_y>h_z\) ,把 \(x\) 和 \(z\) 一组, \(y\) 自己一组,花费为 \(h_x\cdot l_z+h_y\cdot l_y\) ,三个一组花费是 \(h_x\cdot l_z\) ,显然更优。
考虑DP。设 \(f_i\) 表示前 \(i\) 个土地的最小费用,易得: \(f_i=\min\{f_i,f_{j}+h_{j+1}\cdot l_{i}\}\) ,但是时间复杂度为 \(O(n^2)\) ,过不去,考虑优化。
用斜率优化。设 \(k=h_{j+1},b=f_j\) ,那么直线为 \(y=kx+b\) ,那么之前的转移方程就相当于求 \(x=l_i\) 时的 \(y_{min}\)
Code
#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=5e4+10;
int n,a[N],b[N],f[N],q[N],hd,tl,stk[N],top;
struct node{
int a,b;
bool operator < (const node &x) {
return a==x.a?b<x.b:a<x.a;
}
}p[N];
inline int slope(int p,int t){
return f[p]+a[t]*b[p+1];
}
inline bool cross(int t1,int t2,int i){
return 1ll*(f[t1]-f[t2])*(b[i+1]-b[t1+1])<1ll*(f[i]-f[t1])*(b[t1+1]-b[t2+1]);
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].a,&p[i].b);
sort(p+1,p+n+1);
stk[++top]=1;
for(int i=2;i<=n;i++){
while(top&&p[i].b>=p[stk[top]].b) --top;
stk[++top]=i;
}
n=top;
for(int i=1;i<=n;i++) a[i]=p[stk[i]].a,b[i]=p[stk[i]].b;
hd=tl=0;
for(int i=1;i<=n;i++){
while(hd<=tl&&slope(q[hd],i)>slope(q[hd+1],i)) ++hd;
f[i]=f[q[hd]]+a[i]*b[q[hd]+1];
while(hd<=tl&&cross(q[tl],q[tl-1],i)) --tl;
q[++tl]=i;
}
printf("%lld\n",f[n]);
return 0;
}