首页 > 代码库 > Bzoj3675 [Apio2014]序列分割
Bzoj3675 [Apio2014]序列分割
Time Limit: 40 Sec Memory Limit: 128 MB
Submit: 2898 Solved: 1170
Description
Input
输入第一行包含两个整数n,k(k+1≤n)。
Output
输出第一行包含一个整数,为小H可以得到的最大分数。
Sample Input
4 1 3 4 0 2 3
Sample Output
HINT
【样例说明】
在样例中,小H可以通过如下3轮操作得到108分:
1.-开始小H有一个序列(4,1,3,4,0,2,3)。小H选择在第1个数之后的位置
将序列分成两部分,并得到4×(1+3+4+0+2+3)=52分。
2.这一轮开始时小H有两个序列:(4),(1,3,4,0,2,3)。小H选择在第3个数
字之后的位置将第二个序列分成两部分,并得到(1+3)×(4+0+2+
3)=36分。
3.这一轮开始时小H有三个序列:(4),(1,3),(4,0,2,3)。小H选择在第5个
数字之后的位置将第三个序列分成两部分,并得到(4+0)×(2+3)=
20分。
经过上述三轮操作,小H将会得到四个子序列:(4),(1,3),(4,0),(2,3)并总共得到52+36+20=108分。
【数据规模与评分】
:数据满足2≤n≤100000,1≤k≤min(n -1,200)。
Source
动态规划 斜率优化DP
首先需要发现一个性质:
$ a*(b+c)+b*c = ab+ac+bc $
$ (a+b)*c+a*b = ab+ac+bc $
这意味着最优得分和切割顺序无关。
那么我们可以从左往右依次切,这显然是一个可以DP的问题。
斜率优化即可。
刚开始推的是$ f[i][k]=max{f[j][k-1]+(sum[n]-sum[i])*(sum[i]-sum[j])} $
这样跑出来26+s,怎么这么慢啊?难道是这样写方程不适合斜率优化?(得多蠢才能得出这个结论)
于是换成了 $ f[i][k]=max{f[j][k-1]+(sum[i]-sum[j])*sum[j]} $
这样跑出来30+s,喵喵喵?
默默常数优化,除式拆成乘式之类的,卡到了13s
一本满足(并不)
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #define LL long long 7 using namespace std; 8 const int mxn=100010; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13 return x*f;14 }15 int n,K;16 int a[mxn],cnt=0;17 int q[mxn],hd,tl;18 LL smm[mxn];19 LL f[mxn],g[mxn];20 double calc(int j,int k){21 return (g[j]-g[k]-(LL)smm[n]*(smm[j]-smm[k]))/(double)(smm[k]-smm[j]);22 }23 int main(){24 // freopen("in.txt","r",stdin);25 int i,j;26 n=read();K=read();27 for(i=1;i<=n;i++){a[i]=read();if(a[i])a[++cnt]=a[i];}28 n=cnt;K=min(n-1,K);29 for(i=1;i<=n;i++)smm[i]=smm[i-1]+a[i];30 for(i=1;i<=K;i++){31 swap(f,g);32 hd=1;tl=0;33 for(j=1;j<=n;j++){34 while(hd<tl && calc(q[tl-1],q[tl])>calc(q[tl],j-1))tl--;35 q[++tl]=j-1;36 while(hd<tl && calc(q[hd],q[hd+1])<smm[j])hd++;37 int t=q[hd];38 if(hd<=tl)f[j]=g[t]+(LL)smm[n]*smm[j]-smm[j]*smm[j]-smm[n]*smm[t]+smm[j]*smm[t];39 }40 }41 LL ans=0;42 for(i=1;i<=n;i++)ans=max(ans,f[i]);43 printf("%lld\n",ans);44 return 0;45 }
完全体:
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #define LL long long 7 using namespace std; 8 const int mxn=100015; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13 return x*f;14 }15 int n,K;16 int a[mxn],cnt=0;17 int q[mxn],hd,tl;18 LL smm[mxn],smm2[mxn];19 LL f[mxn],g[mxn];20 inline LL calc_up(int j,int k){21 return smm2[k]-smm2[j]+g[j]-g[k];22 }23 inline LL calc_down(int j,int k){24 return smm[k]-smm[j];25 }26 int main(){27 // freopen("in.txt","r",stdin);28 int i,j;29 n=read();K=read();30 for(i=1;i<=n;i++){a[i]=read();if(a[i])a[++cnt]=a[i];}31 n=cnt;32 for(i=1;i<=n;i++)smm[i]=smm[i-1]+a[i],smm2[i]=smm[i]*smm[i];33 for(i=1;i<=K;i++){34 swap(f,g);35 hd=1;tl=0;36 for(j=i;j<=n;j++){37 while(hd<tl && calc_up(q[tl-1],q[tl])*calc_down(q[tl],j-1)>=calc_up(q[tl],j-1)*calc_down(q[tl-1],q[tl]))tl--;38 q[++tl]=j-1;39 while(hd<tl && calc_up(q[hd],q[hd+1])<smm[j]*calc_down(q[hd],q[hd+1]))hd++;40 int t=q[hd];41 f[j]=g[t]+smm[t]*((LL)smm[j]-smm[t]);42 }43 }44 printf("%lld\n",f[n]);45 return 0;46 }
Bzoj3675 [Apio2014]序列分割