魈凯KBS • 4个月前
using namespace std; string s; long long NOI[100010],n,NewN,NewO,NewI; long long N[100010],I[100010]; int main() {
cin>>n; getchar(); getline(cin,s);//输入 s='0'+s;//下标从1开始 for(int i=1; i<=n; i++)//前缀和思想统计N,I {
if(s[i]=='N') N[i]++;
if(s[i]=='I') I[i]++;
N[i]+=N[i-1];
I[i]+=I[i-1];
} for(int i=1; i<=n; i++) {
NewO=max(NewO,N[i-1]*(I[n]-I[i-1]));//插入O时新增NOI的数量
if(s[i]=='O')
{
NOI[i]+=N[i-1]*(I[n]-I[i-1]);//原本NOI的数量
NewN+=I[n]-I[i-1];//插入N时新增NOI的数量
NewI+=N[i-1];//插入I时新增NOI的数量
}
NOI[i]+=NOI[i-1];//前缀和统计原本NOI数量
} cout<<NOI[n]+max(NewO,max(NewN,NewI));//NOI[n]加上插入N,O,I中值最大的 return 0; }
评论: