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 ;
}
