【题解】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)$ 转移即可。

添加新评论