题目理解

我们有一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$（全为正整数），以及一个长度为 $n$ 的字符串 $s$，只包含 'L' 和 'R'。

操作规则：

• 选择一对 $(l, r)$，满足 $1 \le l < r \le n$，$s_l = \text{'L'}$，$s_r = \text{'R'}$
• 获得分数：$a_l + a_{l+1} + \dots + a_r$（即区间 $[l, r]$ 的和）
• 将该区间内所有字符变为 '.'，表示这些位置不能再被使用

目标：最大化总分

关键观察

1. 所有 $a_i > 0$
   这意味着区间和随着区间长度增加而增加。因此，在能选择的情况下，我们总希望选择尽可能大的合法区间。

2. 选择的区间不能重叠（因为一旦使用，其中的字符就变成 '.'，不能再被选为任何区间的端点或内部点）。
   但区间可以嵌套：如果先选一个小区间，之后可以再选包含它的大区间（只要大区间的端点在小区间之外且仍未被使用）。

3. 最优策略的贪心思路
   由于所有数为正，我们应该优先选择当前最左边可用的 'L' 和当前最右边可用的 'R' 组成一个区间。
   为什么？

   • 如果左边还有 'L' 没被用，而右边还有 'R' 没被用，那么选它们之间的区间一定不差于选更小的区间，因为区间和更大。
   • 选完这对 $(l, r)$ 后，$l$ 和 $r$ 被删除，相当于我们“向内收缩”，继续在剩下的子问题中重复这个过程。

4. 等价表述
   将字符串 $s$ 中的 'L' 视为“左括号”，'R' 视为“右括号”，但注意这里的括号匹配不是任意的，而是必须左括号在右括号左边，且我们总是匹配最左边可用的 'L' 与最右边可用的 'R'。

算法步骤

设 $n$ 为长度，$a$ 从 $1$ 开始索引。预处理前缀和：

区间 $[l, r]$ 的和 = $\text{prefix}[r] - \text{prefix}[l-1]$

双指针法：

• 初始化 $l = 0$（对应索引 $0$，因为字符串索引从 $0$ 开始，但为了前缀和方便，$a$ 从 $1$ 开始）
• 初始化 $r = n-1$
• 重复以下步骤直到 $l \ge r$：
  1. 将 $l$ 向右移动，直到 $s[l] = \text{'L'}$（跳过 'R'）
  2. 将 $r$ 向左移动，直到 $s[r] = \text{'R'}$（跳过 'L'）
  3. 如果 $l < r$，则：
     • 区间为 $[l+1, r+1]$（因为数组 $a$ 从 $1$ 开始，而字符串 $s$ 从 $0$ 开始）
     • 和 = $\text{prefix}[r+1] - \text{prefix}[l]$
     • 加到答案
     • $l$ 右移一位，$r$ 左移一位（表示这两个位置已被使用）

示例验证

以第一个样例为例：

n = 6
a = [3,5,1,4,3,2]
s = LRLLLR

前缀和：

初始 $l=0$, $r=5$：

• $s[0]=\text{'L'}$，$s[5]=\text{'R'}$，直接取区间 $[1,6]$，和 = $18-0=18$
  答案 += 18，$l=1$, $r=4$
• 现在 $s[1]=\text{'R'}$ → $l$ 右移到 $2$（$s[2]=\text{'L'}$）
  $s[4]=\text{'L'}$ → $r$ 左移到 $3$（$s[3]=\text{'L'}$），但 $s[3] \ne \text{'R'}$，继续左移到 $2$？等一下，仔细看： 实际过程：$r=4$ 时 $s[4]=\text{'L'}$，所以 $r$ 左移到 $3$，$s[3]=\text{'L'}$ 仍不是 'R'，再左移到 $2$，$s[2]=\text{'L'}$ 也不是 'R'，再左移到 $1$，$s[1]=\text{'R'}$ 是 'R'，停。 此时 $l=2$, $r=1$，$l > r$，循环结束。
• 答案 = 18

为什么这样是对的？

因为所有 $a_i > 0$，如果我们不选当前最左边 'L' 和最右边 'R' 组成的区间，而是选它们内部的区间，那么：

• 外部的 'L' 和 'R' 之后可能无法再配对（因为内部被删掉后，外部端点仍可用，但内部缺失不会影响外部区间的和，反而会变小）
• 更严格地：假设最优解中某次选了 $(l_1, r_1)$，且存在 $l < l_1$ 是 'L'，$r > r_1$ 是 `'R'$都没被用过，那么把这次操作换成$(l, r)$ 会得到更大的和，且不破坏后续操作的可能性（因为区间变大了，删除的更多，后续可选区间是它的子集）。

因此贪心成立。

时间复杂度

$O(n)$ 每个测试用例，总 $O(\sum n)$。

代码实现（已给出）

def solve():
    n = int(input())
    a = [0]
    for x in input().split():
        x = int(x)
        a.append(a[-1] + x)
    s = input()
    ans = 0
    l = 0
    r = n - 1
    while r > l:
        while l < n and s[l] == 'R':
            l += 1
        while r >= 0 and s[r] == 'L':
            r -= 1
        if l < r:
            ans += a[r + 1] - a[l]
            l += 1
            r -= 1
    print(ans)