bzoj 2726: [SDOI2012]任务安排【cdq+斜率优化】

cdq复健.jpg

首先列个n方递推，设sf是f的前缀和，st是t的前缀和：

\[f[i]=min(f[j]+s*(sf[n]-sf[j])+st[i]*(sf[i]-sf[j]))
\]

然后移项：

\[f[i]=f[j]+s*sf[n]-s*sf[j]+st[i]*sf[i]-st[i]*sf[j]
\]

\[f[i]=f[j]+s*sf[n]+st[i]*sf[i]-s*sf[j]-st[i]*sf[j]
\]

\[f[i]=f[j]+s*sf[n]+st[i]*sf[i]-sf[j]*(s+st[i])
\]

\[f[i]+sf[j]*(s+st[i])=f[j]+s*sf[n]+st[i]*sf[i]
\]

然后看成斜率表达式b+kx=y，那么

\[b=f[i]，x=sf[j]，k=(s+st[i])，y=f[j]+s*sf[n]+st[i]*sf[i]
\]

然后因为有负数所以这并不能用单调队列，splay是很方便但是又太长了

选择cdq

和bzoj 1492差不多，只是上凸壳变成下凸壳了，详见https://www.cnblogs.com/lokiii/p/9199587.html

注意！！转移的时候不是f[i]而是f[a[i].id]！！！我简直zz……

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const long long N=500005,inf=1e18;

long long n,s[N],m,dz,f[N];

struct dian

{

	double x,y;

	bool operator < (const dian &b) const

	{

		return (x<=b.x)||(x==b.x&&y<=b.y);

	}

}p[N],q[N];

struct qwe

{

	long long st,sf,k,id;

}a[N],b[N];

bool cmp(const qwe &a,const qwe &b)

{

	return a.k<b.k;

}

long long read()

{

	long long r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

double wk(long long i,long long j)

{

	return (p[i].y-p[j].y)/(p[i].x-p[j].x);

}

void cdq(long long l,long long r)

{

	if(l==r)

	{

		f[l]=min(f[l],(long long)(dz+a[l].st*a[l].sf));

		p[l].x=a[l].sf;

		p[l].y=f[l];

		return;

	}

	long long mid=(l+r)>>1,top=0,l1=l,l2=mid+1;

	for(long long i=l;i<=r;i++)

	{

		if(a[i].id<=mid)

			b[l1++]=a[i];

		else

			b[l2++]=a[i];

	}

	for(long long i=l;i<=r;i++)

		a[i]=b[i];

	cdq(l,mid);

	for(long long i=l;i<=mid;i++)

	{

		while(top>1&&wk(i,s[top])<wk(s[top],s[top-1]))

			top--;

		s[++top]=i;

	}//cerr<<top<<endl;

	for(long long i=mid+1,j=1;i<=r;i++)

	{

		while(j<top&&wk(s[j+1],s[j])<(double)a[i].k)

			j++;//cerr<<i<<"   "<<s[j]<<endl;

		f[a[i].id]=min(f[a[i].id],(long long)(p[s[j]].y+dz+a[i].st*a[i].sf-p[s[j]].x*(m+a[i].st)));

	}

	cdq(mid+1,r);

	l1=l,l2=mid+1;

	for(long long i=l;i<=r;i++)

	{

		if((p[l1]<p[l2]||l2>r)&&l1<=mid)

			q[i]=p[l1++];

		else

			q[i]=p[l2++];

	}

	for(long long i=l;i<=r;i++)

		p[i]=q[i];

}

int main()

{

	n=read(),m=read();

	for(long long i=1;i<=n;i++)

		a[i].st=a[i-1].st+read(),a[i].sf=a[i-1].sf+read(),a[i].k=m+a[i].st,a[i].id=i;

	dz=m*a[n].sf;//cerr<<dz<<"!"<<endl;

	sort(a+1,a+1+n,cmp);

	for(long long i=1;i<=n;i++)

		f[i]=inf;

	cdq(1,n);

	// for(int i=1;i<=n;i++)

		// cerr<<f[i]<<endl;

	printf("%lld\n",f[n]);

	return 0;

}

巴特西

bzoj 2726: [SDOI2012]任务安排【cdq+斜率优化】

最新文章

热门文章