【BZOJ3437】小P的牧场（动态规划，斜率优化）

题面

题解

考虑暴力\(dp\)，设\(f[i]\)表示强制在\(i\)处建立控制站的并控制\([1..i]\)的最小代价。

很显然，枚举上一个控制站的位置\(j\)

\(f[i]=min(f[j]+Calc(i,j)+a[i])\)，其中\(Calc(i,j)\)表示\(i,j\)之间被\(i\)控制的位置产生的贡献。

这个可以用前缀和优化做到\(O(1)\)计算\(Calc\)

预处理\(s1[i]=\sum b[i],s2[i]=\sum (n-i+1)*b[i]\)

那么\(Calc(i,j)=s2[i]-s2[j]-(s1[i]-s1[j])*(n-i+1)\)

考虑两个位置\(j,k\)，满足\(k\lt j\)，并且\(k\)的转移劣于\(j\)

那么

\(f[k]+Calc(i,k)\gt f[j]+Calc(i,j)\)

拆开之后是：

\(f[k]-s2[k]+s1[k]*(n-i+1)\gt f[j]-s2[j]+s1[j]*(n-i+1)\)

令\(g[i]=f[i]-s2[i]+s1[i]*(n+1)\)

将所有项按照是否与\(i\)相关分类，可以得到

\((g[k]-g[j])\gt (s1[k]-s1[j])*i\)

因为\(k<j\)，所以\(s1[k]<s1[j]\)，除过去要变号

\[i>\frac{g[k]-g[j]}{s1[k]-s1[j]}
\]

妥妥的斜率优化，因为\(i\)单增，可以单调队列解决。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

#define RG register

#define MAX 1000100

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n,a[MAX],b[MAX];

int Q[MAX],h,t;

ll f[MAX],s1[MAX],s2[MAX];

ll calc(int i,int j){return f[j]+s2[i]-s2[j]-(s1[i]-s1[j])*(n-i+1)+a[i];}

double Slope(int j,int k)

{

	double gj=f[j]-s2[j]+1.0*s1[j]*(n+1);

	double gk=f[k]-s2[k]+1.0*s1[k]*(n+1);

	return 1.0*(gj-gk)/(s1[j]-s1[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();

	for(int i=1;i<=n;++i)s1[i]=s1[i-1]+b[i];

	for(int i=1;i<=n;++i)s2[i]=s2[i-1]+1ll*(n-i+1)*b[i];

	Q[h=t=1]=0;

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

	{

		while(h<t&&Slope(Q[h],Q[h+1])<=i)++h;

		int j=Q[h];f[i]=calc(i,j);

		while(h<t&&Slope(Q[t],Q[t-1])>=Slope(Q[t-1],i))--t;

		Q[++t]=i;

	}

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

}

巴特西

【BZOJ3437】小P的牧场（动态规划，斜率优化）

【BZOJ3437】小P的牧场（动态规划，斜率优化）

题面

题解

最新文章

热门文章