题解 P1371 【NOI元丹】

· · 题解

博客地址

大意

从左到右，问加了一个'p'后一共有几个noi？（p可以为n，o，i中的一个）长度小于100001

思路

加p之前，noi的个数为每个o之前n的个数*之后i的个数并累加。

加p之后，有三种情况：N，O，I

N肯定是放在第一个O前面方案最多了，每次多出每个O之前N的个数。

I肯定是放在最后一个O后面方案最多了，每次多出每个O之后I的个数。

O的话就要枚举了，枚举每个位置，求出o之前n的个数之后i的个数求之最大值。

从上述三种情况中取出最大值，加上没有p的noi总数即为最优解！

（注：要开long long）

代码


#include<cstdio>
#define U unsigned
#define r(i,a,b) for(int i=a;i<=b;i++)
#define d(j,a,b) for(int j=a;j>=b;j--)
using namespace std;U long long n,ans1;char s[100001];
U long long res_N,res_O,res_I;
U long long ni[100001],ii[100001];
U long long max(U long long x,U long long y) {return x>y?x:y;}
int main()
{
    scanf("%lld\n",&n);
    gets(s);
    r(i,0,n-1) if(s[i]=='I') ii[0]++;//求i总数
    r(i,0,n-1)
     {
        ni[i]=ni[i-1];//取上次的
        ii[i]=max(ii[i-1],ii[i]);//取上次的，max是因为上面用了ii【0】所以要加
        if(s[i]=='N') ni[i]++;//N个数++
        if(s[i]=='I') ii[i]--;//I个数--
        if(s[i]=='O') 
         {ans1+=ni[i]*ii[i];res_N+=ii[i];res_I+=ni[i];}//算
     }
    r(k,0,n-1)//枚举各个位置插入
     res_O=max(res_O,ni[k]*ii[k]);//取最大值
    printf("%lld",ans1+max(res_N,max(res_O,res_I)));//三种方案的最大值
}