[APIO2014]序列分割

这是一道不那么裸的斜率DP,所以感觉有写一下的必要,本篇博文系边推边写而成。

题目内容

我们首先要明确一点,决定最终结果的一定是分割的位置,而不是分割的顺序。

将原始序列分为3段,a,b,c分别表示3段区间的元素和 。
我们如果先从a,b间分割,再从b,c间分割,得分\( a(b+c)+bc=ab+ac+bc \)
而如果先从b,c间分割,再从a,b间分割,得分\( (a+b)c+ab=ab+ac+bc \)
这两种方法得分相同,而分为多个区间完全可以由3区间分割推得,所以划分区间先后顺序不影响答案。

f[i,j]表示在i处分割,已分割了j次,s[i]表示1-i的前缀和,tot=s[n]。

然后设a<b<i,我们在i处进行分割操作,此时分割了k次,上一次分割是a处

\[ f[i,k]=f[a,k-1]+(s[i]-s[a])(tot-s[i]) \]

可以推得

\begin{cases}
x(a)=f[a,k-1]-tot*s[a]\\
f[i,k]=x(a)+s[i](tot-s[i])+s[i]s[a]
\end{cases}

如果决策点a优于b (a<b)

\[ x(a)+s[i]s[a] > x(b)+s[i]s[b] \]

\[ \frac{x(a)-x(b)}{s[a]-s[b]} < -s[i] \]

我们把k从1-k循环,每次做一遍斜率优化的DP即可,f数组可以滚动,时间O(nk),空间O(n)。


然后我发现这个式子导致了一大堆毫无意义的特殊情况和讨论,正确性是毋庸置疑的,但是我成功WA了。于是我决定采用一种比调试更有效率的方法——更换DP方程。

f[i,j] 表示前i段分了j次得到的最优分数。

\[ f[i,j]=max(  f[k,j-1]+(s[i]-s[k])s[k] )  \]

由此可得:

\begin{cases}
x(a)=f[a,j-1]-s[a] ^ 2\\
f[i,k]=x(a)+s[i]s[a]
\end{cases}

如果决策点a优于b (a<b)

\[ x(a)+s[i]s[a] > x(b)+s[i]s[b] \]

\[ \frac{x(a)-x(b)}{s[a]-s[b]} < -s[i] \]

本题还有一个小问题,由于可能有0的存在(详见样例),s[a]-s[b]可能为0,所以在读入的时候删去那些值为0的点,它们对答案没有影响。


 

点赞

发表评论

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