50求助!!
查看原帖
50求助!!
235657
hwx12233楼主2020/5/12 18:27
#define int ll

inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}

const int N=1e5+10;

struct node{
	int w,l;
}a[N],b[N];
int n,n1,q[N],head=1,tail=1,x[N],y[N],f[N];
inline bool cmp(node x,node y){return x.l==y.l?x.w<y.w:x.l<y.l;}
inline long double slope(int q,int w){return (y[q]-y[w])/(x[q]-x[w]);}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].w>>a[i].l;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		while(n1&&b[n1].w<=a[i].w)n1--;
		b[++n1].l=a[i].l;b[n1].w=a[i].w;
	}
	for(int i=1;i<=n1;i++){
		while(head<tail&&slope(q[head],q[head+1])<b[i].l)head++;
		f[i]=f[q[head]]+b[q[head]+1].w*b[i].l;x[i]=-b[i+1].w;y[i]=f[i];
		while(head<tail&&slope(i,q[tail])<slope(q[tail],q[tail-1]))tail--;
		q[++tail]=i;
	}
	cout<<f[n1];
}

求巨佬解答

2020/5/12 18:27
加载中...