BZOJ1597 USACO2008土地购买

斜率优化DP。
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=5e5+10;
 4 long long f[N],n,cnt,q[N];
 5 double eps=1e-9;
 6 bool v[N];
 7 struct node{
 8     long long x,y;
 9     bool operator<(const node &b)const{
10         if(x==b.x)return y<b.y;
11         return x<b.x;
12     }
13 }a[N],b[N];
14 double calc(int x,int y)
15 {
16     return (double)(f[x]-f[y])/(b[y+1].y-b[x+1].y);
17 }
18 void solve()
19 {
20     int l=1,r=1;q[1]=0;
21     for(int i=1;i<=cnt;++i)
22     {
23         while(l<r&&calc(q[l],q[l+1])<=b[i].x)l++;
24         f[i]=f[q[l]]+1ll*b[i].x*b[q[l]+1].y;
25         while(l<r&&calc(q[r-1],q[r])>=calc(q[r],i))r--;
26         q[++r]=i;
27     }
28     return;
29 }
30 int main()
31 {
32     scanf("%d",&n);
33     for(int i=1;i<=n;++i)
34     {
35         scanf("%lld%lld",&a[i].x,&a[i].y);
36     }
37     sort(a+1,a+1+n);
38     for(int i=1;i<=n;++i)
39     {
40         while(cnt>0&&a[i].y>=b[cnt].y)cnt--;
41         b[++cnt]=a[i];
42     }
43     solve();
44     printf("%lld
",f[cnt]);
45     return 0;
46 }