洛谷P1371 NOI元丹

题目描述

小A打算开始炼NOI元丹（什么鬼），据说吃了可以提高NOI时的成绩。

是这么练的。元丹有三种元核，'N','O','I'。现有很多个这样原核，按顺序排成一行。炼元丹时，从左往右分别挑出'N','O','I'三个原核吞下。

现在他关心，有几种服用方式……且慢！

他觉得服用方式太少，以至于不能成仙。所以他可以通过某个途径，得到'N','O','I'的三种原核中的任意一个，至于哪一种由他决定。然后他将获得这个原核的插入到这一排原核中的任意位置（包括最前最后）。

现在你要知道，新的元核序列中能有多少种'N','O','I'的取出方式。子串的字母并不要求连续。

输入输出格式

输入格式：

第一行，一个整数N，表示字符串的长度。

第二行，一行字符串，里面只有只有'N','O','I'三种字母。

输出格式：

表示出最多可以提炼出来的NOI元丹的方案种数。

输入输出样例

输入样例#1：

5
NOIOI

输出样例#1：

说明

样例解释

他可以获取一个N元核，加到最前面。

NNOIOI | NNOIOI | NNOIOI | NNOIOI | NNOIOI | NNOIOI
~ ~~   | ~ ~  ~ | ~   ~~ |  ~~~   |  ~~  ~ |  ~  ~~

30%的数据N<=200

50%的数据N<=2000

100%的数据3<=N<=100000

前缀和+递推

先算出不加字母的方案数：

　　枚举每个O的位置，累加 O前的N个数*O后的I个数

　　↑这步可以同时记录最大的乘积，即是加一个O得到的最大收益

若加N，肯定加在最前面

　　可增加的方案数：枚举O的位置，累加O后的I个数

若加I，肯定加在最后面

　　可增加的方案数：枚举O的位置，累加O前的N个数

三个方案取max即可

顺便吐槽一下，昨晚做这题的时候，因为急着去洗澡（怕水放凉），代码里只写了原方案数和加O的方案数就交上去，成功过掉了1/3的点

23333

 1 /*By SilverN*/
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<algorithm>
 7 #define LL long long
 8 using namespace std;
 9 const int mxn=100001;
10 LL cn[mxn],co[mxn],ci[mxn];
11 char s[mxn+10];
12 int n;
13 int main(){
14     scanf("%d",&n);
15     scanf("%s",s+1);
16     for(int i=1;i<=n;++i){
17         cn[i]+=cn[i-1];
18         co[i]+=co[i-1];
19         ci[i]+=ci[i-1];
20         if(s[i]=='N') ++cn[i];
21         if(s[i]=='O') ++co[i];
22         if(s[i]=='I') ++ci[i];
23     }
24     LL ans=0;LL tmp=0;LL mxt=0;
25     for(int i=1;i<=n;++i){
26         if(s[i]!='O')continue;
27         tmp=cn[i]*(ci[n]-ci[i]);
28 //        printf("pos:%d tmp:%lld
",i,tmp);
29         ans+=tmp;
30         if(tmp>mxt)mxt=tmp;
31     }
32     LL tn=0,ti=0;
33     for(int i=1;i<=n;++i)if(s[i]=='O')tn+=ci[n]-ci[i];
34     for(int i=1;i<=n;++i)if(s[i]=='O')ti+=cn[i];
35 //    printf("%lld %lld %lld
",tmp,tn,ti);
36     ans=max(tmp,max(tn,ti))+ans;
37     cout<<ans<<endl;
38     return 0;
39 }