Luogu-3648 [APIO2014]序列分割

题解：

首先要发现一个重要的性质：分割的顺序是不会影响答案的

证明：

首先对于没有交的两段区间，显然先后顺序改变不会有影响

而对于在同一段区间上的两次分割：

设有一段序列由长度为\(x,y,z\)的三段拼接起来

如果先分割\(xy\)和\(z\)，再分割\(x\)和\(y\)，答案是\((x+y)*z+x*y\)

而如果先分割\(x\)和\(yz\)，再分割\(y\)和\(z\)，答案是\(x*(y+z)+y*z\)

可以发现，两个答案都是\(xy+xz+yz\)，即分割顺序不影响答案

这样我们就可以愉快地DP啦

设\(f[i][j]\)为将\(1\sim i\)这段分割\(j\)次产生的代价，\(s[i]\)为\(1\sim i\)段的总长，则有：

\[f[i][j]=f[k][j-1]+s[k]*(s[i]-s[k]) \quad k\in [1,i-1]
\]

分割次数这一维可以滚动优化空间，设上一次的为\(g[i]\)，这一次要求的是\(f[i]\)

上面的式子就是

\[f[i]=g[k]+s[k]*(s[i]-s[k]) \quad k\in [1,i-1]
\]

哎，感觉很像可以斜率优化的式子啊，那么...

如果从\(k\)转移比从\(j\)转移更优，则：

\[g[k]+s[k]*(s[i]-s[k]) > g[j]+s[j]*(s[i]-s[j])
\]

再化一化

\[\frac{(g[k]+s[k]*s[k])-(g[j]-s[j]*s[j])}{s[j]-s[k]} >s[i]
\]

于是我们就可以用斜率优化dp啦，

注意这题精度卡的简直丧心病狂...算斜率的时候一定要先算减再乘\(1.0\)

代码

#include<map>

#include<queue>

#include<cmath>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

inline ll read(){

	ll ans=0,fh=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-') fh=-1;

		ch=getchar();

	}

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

		ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();

	return ans*fh;

}

const int maxn=1e5+100;

const long double inf=1e18;

int n,k,st[maxn],tp,pre[210][maxn],q[maxn];

ll s[maxn],f[maxn],g[maxn];

inline long double slope(int x,int y){

	if(s[x]==s[y]) return -inf;

	long double aa=1.0*((g[x]-s[x]*s[x])-(g[y]-s[y]*s[y]));

	return aa/(s[y]-s[x]);

}

int main(){

//	freopen("nh.in","r",stdin);

	//freopen("zhy.out","w",stdout);

	n=read(),k=read();

	for(int i=1;i<=n;i++) s[i]=read()+s[i-1];

	for(int i=1;i<=k;i++){

		int l=1,r=0;q[++r]=0;

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

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

			f[j]=g[q[l]]+s[q[l]]*(s[j]-s[q[l]]);

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

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

			q[++r]=j;

		}

		memcpy(g,f,sizeof(g));

	}

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

	for(int i=pre[k][n];i;i=pre[--k][i]) st[++tp]=i;

	while(tp) printf("%d ",st[tp--]);

	return 0;

}

巴特西

Luogu-3648 [APIO2014]序列分割

Luogu-3648 [APIO2014]序列分割

题解：

代码

最新文章

热门文章