bzoj 3437: 小P的牧场【斜率优化】

时间：2022-12-07 12:29:26

emmm妹想到要倒着推

先假设只在n建一个控制站，这样的费用是\( \sum_{i=1}^{n} b[i]*(n-i) \)的

然后设f[i]为在i到n键控制站，并且i一定建一个，能最多节省下的费用，那么显然转移是\( f[i]=max(f[j]+s[i]*(j-i)-a[i]) \)，s是b的前缀和

然后显然要斜率优化，随便推一推就行了

\[ f[i]=f[j]+s[i]*j-s[i]*i-a[i]
\]

\[-s[i]*j+f[i]=f[j]-s[i]*i-a[i](k=-s[i],x=j,b=f[i],y=f[j]-s[i]*i-a[i])
\]
#include<iostream>

#include<cstdio>

using namespace std;

const int N=1000005;

int n,q[N],l=1,r;

long long a[N],b[N],s[N],f[N],ans;

int read()

{

	int 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(int j,int k)

{

	return (double)(f[j]-f[k])/(double)(j-k);

}

int main()

{

	n=read();

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

		a[i]=read();

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

		b[i]=read(),s[i]=s[i-1]+b[i];

	q[++r]=n;

	for(int i=n-1;i>=1;i--)

	{

		while(l<r&&wk(q[l],q[l+1])<-1.0*s[i])

			l++;

		f[i]=f[q[l]]+s[i]*(q[l]-i)-a[i];

		ans=max(ans,f[i]);

		while(l<r&&wk(q[r],q[r-1])>wk(i,q[r]))

			r--;

		q[++r]=i;

	}

	ans*=-1;

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

		ans+=b[i]*(n-i);

	printf("%lld\n",ans+a[n]);

	return 0;

}

/*

4

2 4 2 4

3 1 4 2

*/

相关文章