DARLING in the FRANXX

利用前缀和预处理出来所有情况的花费 枚举
02老婆这部剧 不通宵刷完真可惜
题目链接
前缀6种情况 取最优
预处理前缀的花费

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
int A[maxn], B[maxn], C[maxn];
char s[maxn];
int num[3];
int main()
{
      std::ios::sync_with_stdio(false);
      int n;
      cin >> n;
      cin >> s + 1;
      int a = 0, b = 0, c = 0;
      for(int i = 1;i <= n;i++)
      {
          if(s[i] != 'A') A[i] = A[i - 1] + 1;
          else A[i] = A[i - 1], a++;
          if(s[i] != 'B') B[i] = B[i - 1] + 1;
          else B[i] = B[i - 1], b++;
          if(s[i] != 'C') C[i] = C[i - 1] + 1;
          else C[i] = C[i - 1], c++;
      }
      int ans = 0x3f3f3f3f;
      //cout << a << " " << b << " " << c << endl;
      //for(int i = 0;i <= n;i++) cout << A[i] << " ";cout << endl;
      //for(int i = 0;i <= n;i++) cout << B[i] << " ";cout << endl;
      //for(int i = 0;i <= n;i++) cout << C[i] << " ";cout << endl;
      for(int i = 1;i <= c + 1;i++)//AB
      {
            int cost = A[i + a - 1] - A[i - 1] + B[i + a + b - 1] - B[i + a - 1];
            cost += C[i - 1] + C[n] - C[i + a + b - 1];
            ans = min(cost, ans);
      }
      for(int i = 1;i <= c + 1;i++)//BA
      {
            int cost = B[i + b - 1] - B[i - 1] + A[i + a + b - 1] - A[i + b - 1];
            cost += C[i - 1] + C[n] - C[i + a + b - 1];
            ans = min(cost, ans);
      }
      for(int i = 1;i <= b + 1;i++)//AC
      {
            int cost = A[i + a - 1] - A[i - 1] + C[i + a + c - 1] - C[i + a - 1];
            cost += B[i - 1] + B[n] - B[i + c + a - 1];
            ans = min(cost, ans);
      }
      for(int i = 1;i <= b + 1;i++)//CA
      {
            int cost = C[i + c - 1] - C[i - 1] + A[i + c + a - 1] - A[i + c - 1];
            cost += B[i - 1] + B[n] - B[i + c + a - 1];
            ans = min(cost, ans);
      }
      for(int i = 1;i <= a + 1;i++)//BC
      {
            int cost = B[i + b - 1] - B[i - 1] + C[i + c + b - 1] - C[i + b - 1];
            cost += A[i - 1] + A[n] - A[i + c + b - 1];
            ans = min(cost, ans);
      }
      for(int i = 1;i <= a + 1;i++)//CB
      {
            int cost = C[i + c - 1] - C[i - 1] + B[i + c + b - 1] - B[i + c - 1];
            cost += A[i - 1] + A[n] - A[i + c + b - 1];
            ans = min(cost, ans);
      }
      cout << ans << endl;
      return 0;
}