ABC303 G 题解

Southern_Dynasty · 2023-05-31 12:53:47 · 题解

区间 DP。

设 f_{l,r} 表示只考虑 [l,r]，先手得分减后手得分的最大值（并不关心谁是先手谁是后手），区间长度 len=r-l+1。

然后对三种情况分别讨论：

• 使用操作一，此时取掉左/右端点的部分先手后手互换，对答案的贡献为 \max(a_l-f_{l+1,r},a_r-f_{l,r-1})。

• 使用操作二，继续分讨：

• 操作三同理：

然后对上述贡献取 \max 就是 f_{l,r} 的值。

用前缀和维护一下即可做到 O(n^3)。

Code

考虑优化。容易发现，此时操作一、操作二和操作三的第一种情况复杂度都是对的。只有操作二、操作三的第二种情况需要枚举长度，时间复杂度 O(n)。

考虑对 len 相同的区间同时处理：记 j=B-i（i 就是操作二转移方程里的，操作三同理），s(l,r) 表示 [l,r] 的区间和。转化一下转移方程：

这个时候我们发现 s(l,r) 和 A 是定值。提出来，就变成了：

现在考虑维护后面这坨东西。

容易发现，[l+i,r-j] 这个区间的长度是不变的，都为 len-B。令 g_i=f_{i,i+len-B-1}+s(i,i+len-B-1)。此时发现方程就是

然后直接用 ST 表维护 \min g_i 即可。对于不同的 len 直接重构即可。时间复杂度 O(n^2\log n)，可以通过此题。

Code