BZOJ【1010】玩具装箱

经典的斜率优化题。

先列出易得的方程:

dp[i]=min{dp[j]+(ij1+sum[i]sum[j]L)^2,dp[i]}  (0j<i)

时间复杂度为O(n^2),显然这是过不了的。

我们定义f[i]=sum[i]+i,C=L+1,那么上式转变成:

dp[i]=min{dp[j]+(f[i]f[j]C)^2,dp[i]}  (0j<i)

假设在i处有两个决策点j,k(j<k),且k的决策比j

可得                         dp[j]+(f[i]f[j]C)dp[k]+(f[i]f[k]C)^2

itf[t]=f[i]+v  (t>i)
我们想知道i对于后面状态t的影响,那么要证明

dp[j]+(f[t]f[j]C)^2>dp[j]+(f[t]f[j]C)^2
dp[j]+(f[i]+vf[j]C)^2 > dp[k]+(f[i]+vf[k]C)^2
dp[j]+(f[i]f[j]C)^2+2v(f[i]f[j]C)+v^2>dp[k]+(f[i]f[k]C)^2+2v(f[i]f[k]C)+v^2

由[1]我们得到
(f[i]−f[j]−C)>(f[i]−f[k]−C)

f[k]>f[j]
展开得到
dp[j]+f[i]^2+(f[j]+C)^2−2⋅f[i]⋅(f[j]+C) > dp[k]+f[i]^2+(f[k]+C)^2−2⋅f[i]⋅(f[k]+C)
dp[j]+(f[j]+C)^2−dp[k]−(f[k]+C)^2 > 2⋅f[i]⋅(f[j]−f[k])

所以可以得到
                               dp[j]dp[k]+(f[j]+C)^2(f[k]+C)^2
斜率slope(j, k) = _________________________________ < f[i]
                                                     2(f[j]f[k])
所以当j<kx(j,k)<f[i]时,我们可以O(1)判断kj,

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]。