这题十分简单
很轻易就能证明,添加原核‘N’时,把它放在最前面增加的最多
添加原核‘I’时,把它放在最后面增加的最多
添加原核‘O’则需一个位一个位的枚举。
正确代码
```
#include<bits/stdc++.h>
using namespace std;
unsigned long long n,ans1,ans2,ans3,ans,cnt,ma;
unsigned long long f[100005],g[100005],a[100005];
string s;
int main() {
cin>>n;
cin>>s;
for(int i=0;i<n;i++) {
if(s[i]=='N') f[i+1]=f[i]+1;
else
f[i+1]=f[i];
if(s[i]=='O')
a[++cnt]=i+1;
}
for(int i=n-1;i>=0;i--) {
if(s[i]=='I') g[i+1]=g[i+2]+1;
else g[i+1]=g[i+2];
if(g[i+1]*f[i+1]>ma) ma=g[i+1]+f[i+1];
}
for(int i=1;i<=cnt;i++) {
ans1+=f[a[i]]*(g[a[i]]+1);
ans2+=(1+f[a[i]])*g[a[i]];
ans3+=f[a[i]]*g[a[i]];
}
ans3+=ma;
ans=max(ans1,max(ans2,ans3));
printf("%lld",ans);
return 0;
}
by I_AM_THREE_BODY_MAN @ 2023-06-09 13:02:28