你试试我的代码
```c
#include<iostream>
#include<cstdio>
#include<string>
#define MAXN 100000
using namespace std;
long long sum=0;
int n;
long long N[MAXN],O[MAXN],I[MAXN];
long long ans[5];
string origin;
int main()
{
cin>>n>>origin;
if(origin[0]=='N') N[0]=1;
if(origin[0]=='O') O[0]=1;
if(origin[0]=='I') I[0]=1;
for(int i=1; i<n; i++)
{
if(origin[i]=='N')
N[i]=N[i-1]+1;
else
N[i]=N[i-1];
if(origin[i]=='O')
O[i]=O[i-1]+1;
else
O[i]=O[i-1];
if(origin[i]=='I')
I[i]=I[i-1]+1;
else
I[i]=I[i-1];
}
for(int i=0;i<n;i++)
if(origin[i]=='O')
sum+=N[i]*(I[n-1]-I[i]);
for(int i=0;i<n;i++)
if(origin[i]=='O')
ans[1]+=(I[n-1]-I[i]);
for(int i=0;i<n;i++)
if(origin[i]=='O')
ans[3]+=N[i];
for(int i=0;i<n;i++)
ans[2]=max(ans[2],N[i]*(I[n-1]-I[i]));
long long res=0;
for(int i=1;i<=3;i++)
res=max(res,ans[i]);
cout<<res+sum<<endl;
return 0;
}
```
@[魔梦](/user/533488)
by JOSEPHzhou @ 2021-12-08 22:12:11
对于原串，枚举每一个O,对于每一个O,假设在x位置,它所产生的NOI数量=N[x]*(I[n]-I[x])
则共可生成sum个NOI串
当添加N的时候，一定在最前面添加新增的NOI会最多,为ans1
当添加I的时候，一定在最后面添加新增的NOI 会最多，为ans3
当添加O的时候，要枚举O 在每一个位置的情况，从每个位置新增加的最大值中选出最大的情况为ans2
比较ans1,2,3的大小 设最大值为res
输出sum+res
by JOSEPHzhou @ 2021-12-08 22:13:29