洛谷P1371 NOI元丹

时间：2020-12-01 10:11:04

P1371 NOI元丹

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

提交  讨论  题解

最新讨论

  • 我觉得不需要讨论O
  • long long 不够
  • 没有取模

题目描述

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

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

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

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

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1： 
5

NOIOI
输出样例#1： 
6

说明

样例解释

他可以获取一个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[], ans,leftt[],rightt[];

string s;

long long dp(string ss)

{

    memset(f, , sizeof(f));

    for (int i = ; i <= n; i++)

    {

        if (ss[i] == 'N')

            f[]++;

        if (ss[i] == 'O')

            f[] += f[];

        if (ss[i] == 'I')

            f[] += f[];

    }

    return f[];

}

string form(int x)

{

    string a;

    for (int i = ; 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 = ; i < n; i++)

    {

        leftt[i] = leftt[i - ];

        if (s[i] == 'N')

            leftt[i]++;

    }

    for (int i = n - ; i; i--)

    {

        rightt[i] = rightt[i + ];

        if (s[i] == 'I')

            rightt[i]++;

    }

    long long t = ,cur = ;

    for (int i = ; 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\n", ans);

    //while (1);

    return ;

}

相关文章