题解 P1371 【NOI元丹】

kkksc03 · 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个数可以预处理一遍。