写这道题时,预处理部分少打了等号,吓得我以为斜率优化错了或者被卡精了 mmp
首先有一个很明显的结论(逃),就是一个土地如果长(\(x\))与宽(\(y\))都比另一个土地小,那么这个土地一定可以跟那另一个一起买,所以这样被包含的土地不会贡献答案.我们只要把长作为第一关键字,宽作为第二关键字,从小到大排个序,然后被包含的土地去掉.这样就剩下一堆\(x\)递增,\(y\)递减的土地.
容易列出转移方程$$f_i=min(f_j+x_iy_{j+1})$$
然而数据范围有50000,n方过不去
发现这题可以用斜率优化,把$$f_j+x_iy_{j+1}<f_k+x_iy_{k+1}$$推一推得到$$x_i<\frac{f_k-f_j}{y_{j+1}-y_{k+1}}$$
然后,,,你懂的
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define db double
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=50000+10;
il LL rd()
{
re LL x=0,w=1;re char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
struct nn
{
LL x,y;
}a[N],b[N];
bool ccmp(nn a,nn b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
int n,m;
LL f[N];
db K(int i,int j){return (db)(f[j]-f[i])/(db)(b[i+1].y-b[j+1].y);}
int main()
{
n=rd();
for(re int i=1;i<=n;i++) a[i].x=rd(),a[i].y=rd();
sort(a+1,a+n+1,ccmp);
for(re int i=1;i<=n;i++)
{
while(m>0&&a[i].y>=b[m].y) --m;
b[++m]=a[i];
}
int q[N],hd=1,tl=1;q[1]=0;
for(re int i=1;i<=m;i++)
{
while(hd<tl&&K(q[hd],q[hd+1])<=b[i].x) ++hd;
f[i]=f[q[hd]]+b[i].x*b[q[hd]+1].y;
while(hd<tl&&K(q[tl],q[tl-1])>=K(i,q[tl-1])) --tl;
q[++tl]=i;
}
printf("%lld\n",f[m]);
return 0;
}