自动搬运

查看原文

来自洛谷，原作者为

	kkksc03 洛谷吉祥物 DA✩ZE

搬运于2025-08-24 21:24:19，当前版本为作者最后更新于2016-10-29 22:04:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好像比T1简单。

首先，假设不加字母，计算NOI个数，可以用O(n)的递推。

for(i=1 to n){
    if(s[i]=='N') then num_N++
    if(s[i]=='O') then num_NO+=num_N
    if(s[i]=='I') then num_NOI+=num_NO
}

要是加一个呢？

容易证明，当加一个'N'时，加到开头会有最多的'NOI';当加一个'I'时，加到末尾会有最多的'NOI'

'O'呢？枚举每一个断点，左边的N个数*右边I个数，然后保留最大值。左边的N个数，右边I个数可以预处理一遍。