P1371 NOI元丹详细题解

O3O_O3O_O3O · 2021-12-28 00:44:50 · 题解

upd on 2022.1.17：

1. 修正了语法错误。

2. 修改了一下 \LaTeX。

在我的博客食用更佳。

大家都知道需要这样解题，但是有的人第一眼看到这样的解题方法可能就会懵：

1. 这个递推代码怎么来的？

3. 怎么 \texttt{AC} 的？

1.这个递推代码怎么来的？

在不插入任何字母的情况下，我们可以把原题理解为先提取 \texttt{OI} 元丹，再提取 \texttt{NO} 元丹，最后整合起来：

提取 \texttt{OI} 元丹：

我们先举几个例子：

这个字符串只有 1 个字母 \texttt{O}，第 1 个字母 \texttt{O} 后只有 1 个字母 \texttt{I}，所以它只有 1 种情况，即 \texttt{0I}。

这个字符串有 2 个字母 \texttt{O}，第 1 个字母 \texttt{O} 后只有 1 个字母 \texttt{I}，第 2 个字母 \texttt{O} 后也只有 1 个字母 \texttt{I}，所以它有 2 种情况，即 \_\texttt{OI} 和 \texttt{O}\_\texttt{I}。

这个字符串只有 1 个字母 \texttt{O} 第 1 个字母 \texttt{O} 后有 2 个字母 \texttt{I}，所以它有 2 种情况，即 \texttt{O}\_\texttt{I} 和 \texttt{OI}\_。

这个字符串有 2 个字母 \texttt{O}，第 1 个字母 \texttt{O} 后有 2 个字母 \texttt{I}，第 2 个字母 \texttt{O} 后有 1 个字母 \texttt{I}，所以它有 3 种情况，即 \texttt{OI}\_~\_、\texttt{O}\_~\_\texttt{I} 和 \_~\_\texttt{OI}。

所以说 \texttt{OI} 元丹的数量是每一个字母 \texttt{O} 后的字母 \texttt{I} 的数量之和。

第一组递归代码就出来了：

for(int i=0;i<str.length();i++){
    if(str[i]=='O'){
        countO+=1;
    }
    else{
        countI+=countO;
    }
}

提取 \texttt{NO} 元丹：

原理与上面一样，只不过代码需要变化一下。

整合后：

for(int i=0;i<str.length();i++){
    if(str[i]=='N'){
        countN++;
    }
    if(str[i]=='O'){
        countO+=countN;//注意这里要改一下
    }
    if(str[i]=='I'){
        res+=countO;
    }
} 

2. \texttt{O} 为什么要插入在那种位置？

上一步完成之后，我们把它放在一个函数里。这是，我们需要考虑插入字母了。插入 \texttt{N} 和 \texttt{I} 都好说，放在最前面和最后面。但是插入 \texttt{O} 时为什么是找一个位置，使这个 \texttt{O} 前面的 \texttt{N} 的数量乘这个 \texttt{O} 后面的 \texttt{I} 的数量最大呢？

我们假设我们把 \texttt{O} 插入到指定位置后前面有 a 个字母 \texttt{N}，后面有 b 个字母 \texttt{I}。还是举提取 \texttt{OI} 元丹和提取 \texttt{NO} 元丹的例子：

提取 \texttt{OI} 元丹：

（只考虑插入的 \texttt{O} 后面的字符串）

由原来的 1 种情况变成 2 种情况（b=1）。

由原来的 3 种情况变成 5 种情况（b=2）。

由原来的 1 种情况变成 3 种情况（b=2）。

我们可以推理出，插入字母 \texttt{O} 后 \texttt{OI} 元丹多了 b 种。

提取 \texttt{NO} 元丹：

（只考虑插入的 \texttt{O} 前面的字符串）

由原来的 1 种情况变成 2 种情况（a=1）。

由原来的 3 种情况变成 5 种情况（a=2）。

由原来的 1 种情况变成 3 种情况（a=2）。

我们可以推理出，插入字母 \texttt{O} 后 \texttt{NO} 元丹多了 a 种。

整合后：

我们可以通过乘法原理得出，插入字母 \texttt{O} 后整个字符串提取出 \texttt{NOI} 元丹的方案种数多了 a\timesb 种。当 a\timesb 最大时，种数最多。所以说插入 \texttt{O} 时需要找一个位置，使这个 \texttt{O} 前面的 \texttt{N} 的数量乘这个 \texttt{O} 后面的 \texttt{I} 的数量最大。

3.怎么 \texttt{AC} 的？

代码奉上（我把我自己写的优化去掉了，提交这个最多 90 分）：

#include<bits/stdc++.h>//万能头文件
using namespace std;
long long F(long long a,string A){
    long long countN=0,countO=0,res=0;
    for(long long i=0;i<A.length();i++){
        if(A[i]=='N'){
            countN++;
        }
        if(A[i]=='O'){
            countO+=countN;
        }
        if(A[i]=='I'){
            res+=countO;
        }
    } 
    return res;
} 
int main(){
    long long a/*题目中的N*/,x[3]={},count=0,countN=0,countI=0,y[100001]={},p;
    string b/*题目中的字符串*/;
    stringstream A;//字符串流，好用但是慢。
    cin >> a >> b;
    A << "N" << b;
    x[0] = F(a+1,A.str());
    A.clear();
    A.str("");
    A << b << "I";
    x[1] = F(a+1,A.str());
    A.clear();
    A.str("");
    for(long long i=0;i<b.length();i++){
        if(b[i]=='N'){
            for(long long j=0;j<=i;j++){
                if(b[j]=='N'){
                    countN++;
                }
            } 
            for(long long j=i;j<b.length();j++){
                if(b[j]=='I'){
                    countI++;
                }
            }
            y[++count] = countN*countI;
            if((y[count]<=y[count-1])&&(count!=0)){//节省时间，为了不TLE
                for(int j=0;j<=p;j++){
                    A << b[p];
                }
                A << "O";
                for(int j=p+1;j<b.length();j++){
                    A << b[p];
                }
                x[2] = F(a+1,A.str());
                goto end;
            }
            countN=0;
            countI=0;
            p = i;
        }
    }
    end:
    sort(x,x+3);
    cout << x[2];
    return 0;//万能尾文件 
}

（审核大人辛苦了）