P1371 NOI元丹

这题看起来就和USACO的一题相似，做起来也差不多，就是多了一步插入

上代码

#include<iostream>
#include<cstdio>
using namespace std;
int l[200000],r[200000];
char a[200000];
long long int s1,s2,s3,st,ans;
int main()
{
    ios::sync_with_stdio(false);
    int i,j,k,n; 
    cin >> n;
    for (i=1; i <= n; i++)
        cin >> a[i];
    for (i=1; i <= n; i++)
        if (a[i]=='N')
            l[i]=l[i-1]+1;
        else
            l[i]=l[i-1];
    for (i=n; i >= 1; i--)
        if (a[i]=='I')
            r[i]=r[i+1]+1;
        else
            r[i]=r[i+1];
    for (i=1; i <= n; i++)
    {
        if (a[i]=='O')
        {
            s1+=(l[i-1]+1)*r[i+1];
            s2+=l[i-1]*(r[i+1]+1);
            s3+=l[i-1]*r[i+1];
        }
    }
    for (i=2; i <= n; i++)
        if (l[i-1]*r[i]>st)
            st=l[i-1]*r[i];
    s3+=st;
    ans=max(s1,max(s2,s3));
    cout << ans << endl;
    return 0;
}

注释：

对于每个$O$，前面$N$的个数乘后面$I$的个数，即为使用此$O$能组成的$NOI$元丹的个数。

如果要插入$N$，那么这个$N$一定插在序列最前面，这样用到的次数最多。

同理，如果要插入$I$，那么这个$I$一定插在序列最后面，与上同理。

若果要插入$O$，则枚举每一个位置，使前面$N$的个数乘后面$I$的个数最大即可