105026 - NOI字符串

题解byRyan123

#include <bits/stdc++.h>
using namespace std;
string s;
long long NOI[100010],n,NewN,NewO,NewI;
long long N[100010],I[100010];
int main()
{

  cin>>n;
  getchar();
  getline(cin,s);//输入
  s='0'+s;//下标从1开始
  for(int i=1; i<=n; i++)//前缀和思想统计N，I
  {
    if(s[i]=='N') N[i]++;
    if(s[i]=='I') I[i]++;
    N[i]+=N[i-1];
    I[i]+=I[i-1];
  }
  for(int i=1; i<=n; i++)
  {
    NewO=max(NewO,N[i-1]*(I[n]-I[i-1]));//插入O时新增NOI的数量
    if(s[i]=='O')
    {
      NOI[i]+=N[i-1]*(I[n]-I[i-1]);//原本NOI的数量
      NewN+=I[n]-I[i-1];//插入N时新增NOI的数量
      NewI+=N[i-1];//插入I时新增NOI的数量
    }
    NOI[i]+=NOI[i-1];//前缀和统计原本NOI数量
  }
  cout<<NOI[n]+max(NewO,max(NewN,NewI));//NOI[n]加上插入N,O,I中值最大的
  return 0;
}