Atcoder Grand Contest 048 题解

可以先判断字典序，如果大于 $\text{atcoder}$ 直接输出 $0$ 就好。

否则从前向后贪心找第一个字典序大于 $a$ 的位置，换到前面就好。

注意：如果这个位置大于 $t$ 那么可以换到第二位。

我们可以先假定所有括号都是圆括号，那么价值就是 $\sum a$ 。

考虑把其中一些括号换成方括号，由于要括号匹配，所有我们肯定一次换两个。

稍微思考可以发现，这两个括号一定一个处于奇数位置，一个偶数位置。

因为合法的括号序列中间元素个数一定是偶数。

那么我们可以把 $b-a$ 作为权值分奇偶排序，每次贪心取最前面的就可以， $<0$ 停止。

我们考虑操作的实质：合并两个段。

若向右移动第 $i$ 只企鹅，那么相当于合并了 $a_{i+1}-a_i-1$ 这个长度。

那么向左就是合并 $a_i-a_{i-1}-1$ 。

考虑到结束状态的 $b_i-b_{i-1}-1$ 是由若干个上面的 $a$ 合并而来，那么问题就转化为了用最少的代价合并出 $b$ 。

我们考虑每一个非0的 $b_i-b_{i-1}-1$ ，每次按顺序选择一个刚好和为它的一个连续区间。这样做一定是正确且最优的。

那么上述操作可以用双指针轻松实现。

注意：每次选取 $a_i-a_{i-1}-1$ 时，要考虑非0的一段，若起始为 $0$ 就要往后缩，保证步数最小。

首先先发现一个性质：一个人只有取完一堆和取一个两种操作。

这分别对应了取完和不取完的情况，而不取完的情况里，只取一个的情况可以转移到其他所有情况，一定不劣于其他选择。

类似 ZJOI取石子游戏，我们可以考虑dp求解。

设 $L[i][j]$ 表示考虑 $[i,j]$ 这个区间内， $a_l$ 至少取什么值能够保证 $Left$ 先手必胜。

类似的， $R[i][j]$ 表示考虑 $[i,j]$ 这个区间内， $a_r$ 至少取什么值能够保证 $Right$ 先手必胜。

我们考虑 $L[i][j]$ 的转移：

如果有人取的 $>1$ ，那么它的消耗速度会大于另外一个人，更早接近边界。

这里的 "边界" 即指 $L[i][j-1]$ 和 $R[i+1][j]$ ，如果有人剩下的石子小于边界的话，那么剩下的一个人直接将 $a_i$ 或 $a_j$ 取完，变为 $[i,j-1]$ 或 $[i+1,j]$ ，这样另一个人就会必败。

所以两人取到边界的时间分别为 $a_i-L[i][j-1]$ 和 $a_r-R[i+1][j]$ ，若要左边必胜，则需在 $Right$ 取过边界时，左边还未取过，即：

a_i-L[i][j-1]\geqslant a_j-R[i+1][j]+1

移项，得：

L[i][j]= a_j-R[i+1][j]+L[i][j-1]+1

$R[i][j]$ 转移类似，总复杂度 $O(Tn^2)$ ，记忆化搜索实现。