洛谷P1371 NOI元丹

- 71通过
- 394提交
题目提供者洛谷OnlineJudge
标签云端评测
难度普及/提高-

讨论题解

题目描述

小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

分析：求方案数，很显然是dp,如果没有插入原核，非常简单，设f[i][j]为字符串前i个字符匹配NOI的第j个字符，显然可以用第i个字符去匹配第j个字符也可以用第i个字符之前的字符去匹配第j个字符，那么f[i][j] = f[i-1][j] + f[i-1][j-1],这种方法比较麻烦，还有一种方法，一个一维数组即可解决问题.

如果要匹配“NO”,如果给定的字符串是“NNOOO”，当我们匹配到第3个字符的时候已经有2种方案了，到第4个字符的时候就有4种方案了，到第5个字符的时候就有5种方案了，每一次都加N的个数，类比到本题，如果出现"N",f[1]++,出现“O”,f[2]+=f[1],出现“I”,f[3]+=f[2],答案就是f[3].

解决完化简后的问题之后，考虑本题，要插入一个原核，一定要是最优插入，那么可以想到N一定插入到最左边，I在最右边，O在中间，前两种情况很好弄，O的情况有点麻烦，记录i位置左边N的个数和右边I的个数，当乘积最大时，在i位置插入O是最优的，这里可以用两个数组维护，因为涉及到多次这种数据的处理，所以先预处理出这两个数组中的数据.

涉及到很多字符串拼凑，所以建议用string.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

long long n, f[4], ans,leftt[100010],rightt[100010];

string s;

long long dp(string ss)
{
    memset(f, 0, sizeof(f));
    for (int i = 0; i <= n; i++)
    {
        if (ss[i] == 'N')
            f[1]++;
        if (ss[i] == 'O')
            f[2] += f[1];
        if (ss[i] == 'I')
            f[3] += f[2];
    }
    return f[3];
}

string form(int x)
{
    string a;
    for (int i = 0; i < x; i++)
        a += s[i];
    a += 'O';
    for (int i = x; i < n; i++)
        a += s[i];
    return a;
}

int main()
{
    scanf("%lld", &n);
    cin >> s;
    string temp;
    temp = 'N' + s;
    ans = max(dp(temp), ans);
    temp = s + 'I';
    ans = max(dp(temp), ans);
    for (int i = 1; i < n; i++)
    {
        leftt[i] = leftt[i - 1];
        if (s[i] == 'N')
            leftt[i]++;
    }
    for (int i = n - 1; i; i--)
    {
        rightt[i] = rightt[i + 1];
        if (s[i] == 'I')
            rightt[i]++;
    }
    long long t = 0,cur = 0;
    for (int i = 1; i < n; i++)
    {
        if (t < leftt[i] * rightt[i])
        {
            t = leftt[i] * rightt[i];
            cur = i;
        }
    }
    temp = form(cur);
    ans = max(dp(temp), ans);
    printf("%lld
", ans);

    //while (1);
    return 0;
}