【题解】CF1421E Swedish Heroes

CF1421E Swedish Heroes

给定长度为 $n$ 的序列 $a_i$，每次可以选择连续的两个数字 $a_x,a_{x+1}$，删去他们，再将 $-(a_x+a_{x+1})$ 插入回原位置。
现在进行 $n-1$ 次操作，求最后剩下的数字的最大值。
$1\le n\le 2\times 10^5,-10^9\le a_i\le 10^9$。

$\texttt{Solution}$

首先有 $\texttt{naive}$ 的 $\mathcal{O}(n^3)$ 的区间 $\texttt{dp}$，但是没有优化余地了。

可以发现每一个位置 $a_i$ 对答案的贡献是 $a_i$ 或者 $-a_i$。

通过手玩所有方案，发现一个结论：

设 $-1$ 个数为 $p$，$+1$ 个数为 $q$，有：

$$2p + q \equiv 1 (\bmod 3)$$

这要怎么发现......

可以数学归纳：

在 $n=1$ 时，显然直接是一个 $+1$，合法。

在 $n-1$ 满足时，合并一个新数，则 $p'=q+1,q'=p$，就有：$2p'+q'=p+2q+2$。因此：

$$2\times (2p'+q')= 2p+4q+4\equiv 3q+5\equiv 2(\bmod 3)$$

则：

$$2p'+q'\equiv 1(\bmod 3)$$

同时，一个方案中必须至少有一对相邻且符号相同的，因为第一次操作之后两个数符号一定相同。现在就可以 $\texttt{dp}$ 了。

设 $dp[i][j][0/1][0/1]$ 表示：前 $i$ 个数字，上式模 $3$ 余 $j$，这一位放的是 $0/1$，前面是否存在至少一个相邻且符号相同的位置的最大答案。

$\mathcal{O}(n)$ 转移即可。