救救孩子……
查看原帖
救救孩子……
113926
typedef楼主2020/10/30 20:05

RT,我遇到蜜汁RE

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int N=3e5+13;
int n,s;
ll c[N],t[N];//sumc,sumt 
ll f[N],q[N];
int main(){
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>c[i];
		t[i]+=t[i-1];
		c[i]+=c[i-1];//处理前缀和 
	}
	int hh=0,tt=0;
	q[0]=0;//f(0)点
	for(int i=1;i<=n;i++){
		//删去该线下方,斜率比该线小的线(点)
		while(hh<tt&&(f[q[hh+1]]-f[q[hh]])<=(t[i]+s)*(c[q[hh+1]]-c[q[hh]])) hh++;
		//上面这是处理一下斜率,防止精度挂掉
		//这里直接拿来用q[hh],是因为q[hh]是凸包中不小于当前线斜率的线的左端点 
		int j=q[hh];
		f[i]=f[j]-(t[i]+s)*c[j]+t[i]*c[i]+s*c[n];//见式,不解释
		//删去此前的线(点),维护凸包性质 
		while(hh<tt&&(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>=(f[i]-f[q[tt]])*(c[q[tt]-c[q[tt-1]]])) tt--;
		//上面这是处理一下斜率,防止精度挂掉
		q[++tt]=i;
	} 
	cout<<f[n]<<endl;
	return 0;
}

救救孩子……

2020/10/30 20:05
加载中...