斜率优化水题
不开long long简直制杖
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
// <1597.cpp> - 07/19/16 20:00:09 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=50010; const int INF=1e9; struct land{ int x,y; bool operator <(const land b) const{return x==b.x?y<b.y:x<b.x;} }a[MAXN]; lol dp[MAXN]; #define k(u,v) double(dp[v-1]-dp[u-1])/(a[v].y-a[u].y) int q[MAXN]; bool v[MAXN]; int main(){ int n=gi(); for(int i=1;i<=n;i++)a[i].x=gi(),a[i].y=gi(); sort(a+1,a+n+1); int maxy=0; for(int i=n;i;i--) if(a[i].y>maxy)v[i]=1,maxy=max(maxy,a[i].y); int t=0; for(int i=1;i<=n;i++)if(v[i])a[++t]=a[i]; n=t; int l=1,r=0; for(int i=1;i<=n;i++){ while(l<r&&k(q[r-1],q[r])<=k(q[r],i))r--; q[++r]=i; while(l<r&&k(q[l],q[l+1])>=-a[i].x)l++; dp[i]=dp[q[l]-1]+1ll*a[i].x*a[q[l]].y; } printf("%lld",dp[n]); return 0; } |
说点什么