#include <bits/stdc++.h>
#define lop(i, a, b) for (int i = a; i < b; i++)
#define pol(i, a, b) for (int i = a; i >= b; i--)
#define debug(x) std::cout << #x " = " << x << std::endl;
using ll = long long;
using namespace std;
void solve() {}
const int N = 2e5 + 5;
int a[N], b[N];
bool vis[N];
string s;
// 能观察到RL处会流失牛奶，且源头是LR。
// 对于每一组RL，左边的连续R和右边的连续L分别计算牛奶总和，它们在每次m都会流失1
// 当他们在某一轮为0之后，不会变为负数。
signed main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  ll n, m;
  cin >> n >> m;
  cin >> s;
  ll ans = 0, sum = 0;

  lop(i, 0, n) {
    cin >> a[i];
    sum += a[i];
  }
  lop(i, n, 2 * n) {
    int j = i % n, k = (i + 1) % n;
    if (vis[j] || vis[k])
      continue;
    if (s[j] == 'R' && s[k] == 'L') {
      vis[j] = vis[k] = 1;
      j--;
      k++;
      ll cnt = 0;
      while (!vis[k] && s[k] == 'L') {
        cnt += a[k];
        vis[k] = 1;
        k++;
        k %= n;
      }
      ans += min(m, cnt);
      cnt = 0;
      while (!vis[j] && s[j] == 'R') {
        cnt += a[j];
        vis[j] = 1;
        j--;
      }
      ans += min(m, cnt);
    }
  }
  if (ans)
    cout << sum - ans;
  else
    cout << sum;
  return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla