传送门
终究还是通宵了啊。。。
这是一道简单的斜率优化dp。
先对所有土地排序，显然如果有严格小于的两块土地不用考虑小的一块。
于是剩下的土地有一条边单增，另外一条单减。
我们假设a[i]是单减的，b[i]是单增的。
f[i]=min(f[j]+a[j+1]∗b[i])" role="presentation" style="position: relative;">f[i]=min(f[j]+a[j+1]∗b[i])f[i]=min(f[j]+a[j+1]∗b[i])
对于两个决策k1<k2" role="presentation" style="position: relative;">k1<k2k1<k2，如果k2优于k1，那么：
f[k1]−f[k2]>b[i]∗(a[k2+1]−a[k1+1])" role="presentation" style="position: relative;">f[k1]−f[k2]>b[i]∗(a[k2+1]−a[k1+1])f[k1]−f[k2]>b[i]∗(a[k2+1]−a[k1+1])
注意a是单减的除过去要变号。
<=>slope<b[i]" role="presentation" style="position: relative;">slope<b[i]slope<b[i]
于是可以斜率优化了。
代码：
#include<bits/stdc++.h>
#define N 50005
#define ll long long
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,tot=0,hd,tl,q[N];
ll f[N];
struct Node{ll a,b;}p_[N],p[N];
inline bool cmp(Node a,Node b){return a.a==b.a?a.b>b.b:a.a>b.a;}
inline double slope(int i,int j){return (f[i]-f[j])*1.0/(p[j+1].a-p[i+1].a);}
int main(){
n=read(),hd=tl=1;
for(int i=1;i<=n;++i)p_[i].a=read(),p_[i].b=read();
sort(p_+1,p_+n+1,cmp);
for(int i=1;i<=n;++i)if(tot==0||p_[i].b>p[tot].b)p[++tot]=p_[i];
for(int i=1;i<=tot;++i){
while(hd<tl&&slope(q[hd],q[hd+1])<p[i].b)++hd;
int j=q[hd];
f[i]=f[j]+p[i].b*p[j+1].a;
while(hd<tl&&slope(q[tl],i)<slope(q[tl-1],q[tl]))--tl;
q[++tl]=i;
}
cout<<f[tot];
return 0;
}