Codeforces D.Right Left Wrong（双指针 + 贪心 + 前缀和）

Vlad found a strip of n cells, numbered from left to right from 1 to n. In the i-th cell, there is a positive integer ai and a letter si, where all si are either 'L' or 'R'.

Vlad invites you to try to score the maximum possible points by performing any (possibly zero) number of operations.

In one operation, you can choose two indices l and r (1≤l<r≤n) such that sl = 'L' and sr = 'R' and do the following:

• add al+al+1+⋯+ar−1+ar points to the current score;
• replace sisi with '.' for all l≤i≤r, meaning you can no longer choose these indices.

For example, consider the following strip:

You can first choose l=1，r=2 and add 3+5=8 to your score.

Then choose l=3， r=6 and add 1+4+3+2=10 to your score.

As a result, it is impossible to perform another operation, and the final score is 18.

What is the maximum score that can be achieved?

Input

The first line contains one integer tt (1≤t≤10^4) — the number of test cases.

The first line of each test case contains one integer nn (2≤n≤2⋅10^5) — the length of the strip.

The second line of each test case contains nn integers a1,a2,…,an (1≤ai≤10^5) — the numbers written on the strip.

The third line of each test case contains a string ss of nn characters 'L' and 'R'.

It is guaranteed that the sum of the values of nn across all test cases does not exceed 2⋅10^5

Output

For each test case, output one integer — the maximum possible number of points that can be scored.

题目大意

有一个长度为 n 的序列 s，si​ 要么是 l，要么是 r。对于 ∀si 都有一个价值 ai​。每次可选择一个 l 和一个 r，记作 sl,sr​，获得 al+al+1+⋯+ar−1+ar 的价值。每次操作后自动将 si(i∈[l,r])si​(i∈[l,r]) 置为 .，即不可再次选择。求最大价值。

保证 ai≥1。

思路

贪心：每一次最大化利益，我们发现离的越远，能获得的分就越高，那么我们双指针l、r从左往右、从右往左，慢慢划直到l >= r停下

代码

#include <iostream>
#define ll long long

using namespace std;

const int N = 2e5 + 10;
int a[N];
ll b[N];

int t, n;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = b[i - 1] + a[i];
    }
    string s;
    cin >> s;
    s = "|" + s;  

    int l = 1, r = n;
    ll res = 0;

    while (l < r) {
        while (l < r && s[l] != 'L') l++;
        while (l < r && s[r] != 'R') r--;
        if (l < r) {
            res += b[r] - b[l - 1];
            l++;
            r--;
        }
    }

    cout << res << endl;
}

int main() {
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

加油 

原文地址：https://blog.csdn.net/AuRoRamth/article/details/142496408

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！