CF426C - 加强版 题解

· · 题解

我们注意到本题的答案是区间最大和的形式。那么答案必定是经过若干次修改之后的一个区间的和。我们设这个区间为 [l, r]，进行 dp。
我们从前往后 dp，设 dp_{i,j,in,out} 表示目前 dp 到 i，j \in \{0,1,2\} 表示当前状态（稍后解释），假想的区间已经有 in 个数被换进去，out 个数被换出去。显然地，我们只有当 in=out 时才能统计答案。

使用记忆化搜索进行 dp。设 f(i, j, in, out) 为记忆化搜索函数。我们的目标就是求出 f 的递推式，即转移方程。 我们对 j 进行分类讨论。

第一种情况，j=0，dp 到 i 时区间还未开始。分两类讨论：

第二种情况，j=1，dp 到 i 时区间已经开始。那么如果 i 不被换出，则用 f(i+1,1,in,out)+a_{i} 来更新答案。如果 i 被换出，用 f(i+1,1,in,out+1) 更新答案。如果区间在 i 时结束，用 f(i+1,2,in,out) 更新答案。

最后一种情况，j=2，dp 到 i 时区间已经结束。那么如果 i 被换进去，则用 f(i+1,2,in+1,out)+a_{i} 更新答案。如果没有，用 f(i+1,2,in,out) 更新答案。

我们汇总以上结果，得到：

f(i,j,in,out)=\begin{cases} 0 & ,i \gt n,j\neq 0,in=out \\ -\infty & ,i\gt n(\mathrm{otherwise}) \\ \mathrm{max}(f(i+1,0,in+1,out)+ a_{i},\kern{3pt}f(i+1,0,in,out),\kern{3pt}f(i+1,1,in,out+1),\kern{3pt}f(i+1,1,in,out)+a_{i}) & ,j=0 \\ \mathrm{max}(f(in+1,1,in,out)+a_{i},\kern{3pt} f(in+1,1,in,out+1),\kern{3pt}f(i+1,2,in,out)) & ,j=1 \\ \mathrm{max}(f(i+1,2,in+1,out)+a_{i},\kern{3pt}f(i+1,2,in,out) & ,j=2\end{cases}

还需要处理一些细节，这里不再展开叙述。时间复杂度为 O(nk^{2})。