BZOJ【3675】序列分割

【描述】

一串数列,每次将其分成两段,并求每次乘积的和的最大值。

对于一个最终分成a/bc/d的序列,我们可以发现无论怎么分,最后得到的答案都是一样的:

1.a/bcd

a/bc/d

ans = a * (b + c + d) + (b + c) * d = ab + ac + cd + bd + cd

2.abc/d

a/bc/d

ans = (a + b + c) * d + a * (b + c) = ab + ac +cd + bd + cd。

所以相当于分割的顺序没有什么用,答案都是每i段乘于前 i - 1段的和。

于是我们可以得到一个动态方程:

f[i][j]=max{f[i1][k]+sum[k]×(sum[j]sum[k])}

表示把前j个数分成i段的最大值,其中j > k。

设1 < a < b < j。

若b的方案比a优,则

f[i-1][b] + sum[b]*(sum[j]-sum[b]) > f[i-1][a] + sum[a]*(sum[j]-sum[a])

f[i-1][b]-f[i-1][a]> sum[a]*sum[j]-sum[a]^2 -sum[b]*sum[j]+sum[b]^2

f[i-1][b]-f[i-1][a]+sum[a]^2-sum[b]^2>(sum[a]-sum[b])*sum[j]

 

f[i-1][b]-f[i-1][a]+sum[a]^2-sum[b]^2

_______________________________________ > sum[j]

sum[a]-sum[b]

 

f[i-1][a]-f[i-1][b]-sum[a]^2+sum[b]^2

_______________________________________ < sum[j]

sum[a]-sum[b]

又sum[j]是一个常数

于是这题就可以用斜率优化来O(1)求出f[i][j]。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注