题目要求的很简单，就是问一个任意加了 $ N,O,I $ 三个字母中的任意一个打的字符串里面能组成几个 $ NOI $ 。
先考虑不加字母的情况，直接枚举每一个 $ O $ 的前后 $ N $ 和 $ I $ 的数量相乘然后累加起来，最后就是答案，可以打出如下代码。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n;
string s;
long long a[N+5],b[N+5],ans;//a表示N的数量,b表示I的数量
int main()
{
cin>>n>>s;
s='@'+s;
for(int i=1;i<=n;++i)
{
a[i]=a[i-1],b[i]=b[i-1];
if(s[i]=='N')a[i]++;
else if(s[i]=='I')b[i]++;
}
for(int i=1;i<=n;++i)
if(s[i]=='O')ans+=a[i]*(b[n]-b[i]);//累加O前N的数量和O后I的数量的乘积
printf("%lld",ans);
return 0;
}
然后再考虑加字母的情况，简单分析不加字母的代码可以知道：
如果加字母 $ N $ ，使每个字母 $ O $ 前有最多的字母 $ N $ 时答案最大，那么 $ N $ 应该加在字符串的开头。
如果加字母 $ O $ ，就要枚举每个位置，选当前位置前N的数量I的数量的乘积最大的地方加入时答案最大。
如果加字母 $ I $ ，使每个字母 $ O $ 后有最多的字母 $ I $ 时答案最大，那么 $ I $ 应该加在字符串的结尾。
最后再将加三种不同字母的答案中最大的输出即可。
然后就可以写出本题的代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n;
string s;
long long a[N+5],b[N+5],ans[4],maxs;
int main()
{
cin>>n>>s;
s='@'+s;
for(int i=1;i<=n;++i)
{
a[i]=a[i-1],b[i]=b[i-1];
if(s[i]=='N')a[i]++;
else if(s[i]=='I')b[i]++;
}
for(int i=1;i<=n;++i)
{
if(s[i]=='O')
{
ans[1]+=(a[i]+1)*(b[n]-b[i]);//ans[1]求在开头加字母N的情况
ans[2]+=a[i]*(b[n]-b[i]),maxs=max(maxs,a[i]*(b[n]-b[i]));//ans[2]求不加任何字母的情况，然后maxs记录在每个位置加O可以得到最大的N与I数量的乘积，最后将ans[2]与maxs想加即为加字母O最大的答案
ans[3]+=a[i]*(b[n]-b[i]+1);//ans[3]求在结尾加字母I的情况
}
}
ans[2]+=maxs;//得出加字母O的最大答案
sort(ans+1,ans+4);//排序一下加三种字母得到的答案
printf("%lld",ans[3]);//输出三个答案中最大的答案
return 0;
}