# bzoj 1597 [Usaco2008 Mar] 土地购买 题解【斜率优化】【DP】【贪心】

## Sample Input

4
100 1
15 15
20 5
1 100


## Sample Output

500


## HINT

John 分 $3$ 组买这些土地:

## 题解：

$$f[i]=\min_{0\le j<i}\left\{f[j]+a_i\times\max_{j<k<i}\left\{b_k\right\}\right\}$$

$$f[i]=\min_{0\le j<i}\left\{f[j]+a_ib_{j+1}\right\}$$

$$f[i]=f[j]+a_ib_{j+1}\\ f[j]=-a_ib_{j+1}+f[i]\\ y=kx+b$$

## Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
struct plot
{
int a,b;
friend bool operator <(plot A,plot B)
{
if(A.a!=B.a)
return A.a<B.a;
return A.b<B.b;
}
}a[50050];
int q[50050],l=0,r=0;
ll f[50050],x[50050],y[50050],nxt[50050];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&a[i].a,&a[i].b);
std::sort(a+1,a+1+n);
for(int i=n;i>=1;)
{
int t=i-1;
while(t&&a[t].b<=a[i].b)
--t;
nxt[t]=i;
i=t;
}
q[++r]=0;
x[0]=a[nxt[0]].b;
for(int i=nxt[0];i;i=nxt[i])
{
ll k=-a[i].a;
while(r-l>=2&&y[q[l+2]]-y[q[l+1]]<k*(x[q[l+2]]-x[q[l+1]]))
++l;
f[i]=y[q[l+1]]-k*x[q[l+1]];
x[i]=a[nxt[i]].b;
y[i]=f[i];
while(r-l>=2&&(y[i]-y[q[r]])*(x[q[r]]-x[q[r-1]])>(y[q[r]]-y[q[r-1]])*(x[i]-x[q[r]]))
--r;
q[++r]=i;
}
printf("%lld\n",f[n]);
return 0;
}


Subscribe

/* */