Loading... #题目描述 弗拉德找到了一条由$n$个单元格组成的条带，从左到右编号为$1$到$n$。在第$i$个单元格中，有一个正整数$a_i$和一个字母$s_i$，其中所有$s_i$要么是'L'，要么是'R'。 弗拉德邀请您尝试通过执行任意(可能为零)次操作来获得最大可能的分数。 在一次操作中，您可以选择两个索引$l$和$r$($1 \le l \le r \le n$)，使得$s_l$='L'且$s_r$='R'，然后执行以下操作： - 将$a_l + a_{l + 1} + \dots + a_{r - 1} + a_r$分数添加到当前分数中； - 将所有$l \le i \le r$的$s_i$替换为'.'，表示您不能再选择这些索引。 例如，考虑以下条带： | $3$ | $5$ | $1$ | $4$ | $3$ | $2$ | | --- | --- | --- | --- | --- | --- | | L | R | L | L | L | R | 您可以首先选择$l = 1$，$r = 2$，并将$3 + 5 = 8$添加到您的分数中。 | $3$ | $5$ | $1$ | $4$ | $3$ | $2$ | | --- | --- | --- | --- | --- | --- | | . | . | L | L | L | R | 然后选择$l = 3$，$r = 6$，并将$1 + 4 + 3 + 2 = 10$添加到您的分数中。 | $3$ | $5$ | $1$ | $4$ | $3$ | $2$ | | --- | --- | --- | --- | --- | --- | | . | . | . | . | . | . | 因此，无法执行另一次操作，并且最终得分为$18$。 可以达到的最大分数是多少？ # 输入 **输入** 第一行包含一个整数 $t$ ($1 \le t \le 10^4$) — 测试用例的数量。 每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) — 条带的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — 条带上写的数字。 每个测试用例的第三行包含一个由 $n$ 个字符 'L' 和 'R' 组成的字符串 $s$。 保证所有测试用例中 $n$ 值的总和不超过 $2 \cdot 10^5$。 # 输出 **输出** 对于每个测试用例，输出一个整数 - 可以获得的最大可能分数。 # 解题思路 阅读题目不难发现， 假设存在这样的序列$L_1...L_2...R_1...R_2$, 则为了让结果最大， 最优的方法是先选择$[L_2, R_1]$在选择$[L_1, R_2]$， 这样可以让$[L_2, R_1]$被遍历两次 按照上述思路， 不难发现这道题可以用贪心的思路解决： - 为了让结果尽可能大， 我们需要让每一个区间尽可能的大 - 为了让每个区间尽可能大， 可以采用逆向思维的过程， 即先考虑最后选择的区间， 只要保证后一次选择的区间不包括前一次选择的区间的端点即可 - 为此可以采用双指针算法， 通过对撞指针来遍历整个数组， 并使用前缀和算法来优化时间复杂度 # AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #define endl '\n' using namespace std; const int N = 2e5 + 10; typedef long long LL; int a[N]; LL pre[N]; char s[N]; int t, n; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t --) { cin >> n; for(int i = 1; i <= n; i ++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; } for(int i = 1; i <= n; i ++) cin >> s[i]; int i = 1, j = n; LL ans = 0; while(i < j) { while(i <= n && s[i] != 'L') i ++; while(j >= 1 && s[j] != 'R') j --; if(i < j && s[i] == 'L' && s[j] == 'R') ans += pre[j] - pre[i - 1]; j --, i ++; } cout << ans << endl; } return 0; } ``` 最后修改：2025 年 01 月 11 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏