bzoj 3675: [Apio2014]序列分割【斜率优化dp】

首先看这个得分方式，容易发现就相当于分k段，每段的值和两两乘起来。

这样就很容易列出dp方程：设f[i][j]为到j分成分成i段，转移是

\[f[i][j]=max { f[k][j]+s[k]*(s[j]-s[k]) }
\]

然后显然这个可以斜率优化，随便推一推式子，假设k选p大于选q，那么

\[f[p][j]+s[p]*(s[j]-s[p])>f[q][j]+s[q]*(s[j]-s[q])
\]

\[f[p][j]+s[p]*s[j]-s[p]^2>f[q][j]+s[q]*s[j]-s[q]^2
\]

\[f[p][j]-f[q][j]-s[p]^2+s[q]^2>s[j]*(s[q]-s[p])
\]

\[\frac{f[p][j]-f[q][j]-s[p]^2+s[q]^2}{s[q]-s[p]}>s[j]
\]

维护一个斜率单调的队列即可。

注意s[q]-s[p]可能是0，所以要特判一下

#include<iostream>

#include<cstdio>

using namespace std;

const int N=100005;

int n,m,to[205][N],q[N];

long long s[N],f[2][N];

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;

}

inline double wk(int r,int j,int k)

{

    if(s[j]==s[k])

		return -1e18;

    return (f[r&1^1][k]-s[k]*s[k]-f[r&1^1][j]+s[j]*s[j])*1.0/(s[j]-s[k]);

}

int main()

{

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

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

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

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

	{

		int l=0,r=0;

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

		{

			while(l<r&&wk(i,q[l],q[l+1])<=s[j])

				l++;

			to[i][j]=q[l];

			f[i&1][j]=f[(i&1)^1][q[l]]+s[q[l]]*(s[j]-s[q[l]]);

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

				r--;

			q[++r]=j;

		}

	}

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

	for(int i=m,u=n;i>=1;i--)

	{

		u=to[i][u];

		printf("%d ",u);

	}

	return 0;

}#include<iostream>

#include<cstdio>

using namespace std;

const int N=100005;

int n,m,to[205][N],q[N];

long long s[N],f[2][N];

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;

}

inline double wk(int r,int j,int k)

{

    if(s[j]==s[k])

		return -1e18;

    return (f[r&1^1][k]-s[k]*s[k]-f[r&1^1][j]+s[j]*s[j])*1.0/(s[j]-s[k]);

}

int main()

{

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

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

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

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

	{

		int l=0,r=0;

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

		{

			while(l<r&&wk(i,q[l],q[l+1])<=s[j])

				l++;

			to[i][j]=q[l];

			f[i&1][j]=f[(i&1)^1][q[l]]+s[q[l]]*(s[j]-s[q[l]]);

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

				r--;

			q[++r]=j;

		}

	}

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

	for(int i=m,u=n;i>=1;i--)

	{

		u=to[i][u];

		printf("%d ",u);

	}

	return 0;

}

巴特西

bzoj 3675: [Apio2014]序列分割【斜率优化dp】

最新文章

热门文章