自动搬运

查看原文

来自洛谷，原作者为

	Nuyoah_awa 事实证明，你没让我失望。

搬运于2025-08-24 22:46:09，当前版本为作者最后更新于2023-04-02 21:45:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定一个字符串，求这个字符串所以子段中 bessie 出现的数量。

题目分析

思路：dp。

我们观察一个子段的值是子段中 bessie 的数量，我们可以考虑把这个值分开来算。

我们定义 $dp[i]$ 表示以 $i$ 结尾的字串中 bessie 的数量。我们从第 $i$ 位倒过来找 bessie，第一个 bessie 的 b 在第 $j$ 位。

转移方程为：

答案为:

其中 $j$ 表示 $s[1…i],s[2…i],……,s[j…i]$ 都会把最后那个 $bessie$ 包含一次，$dp[j-1]$ 表示以 $j-1$ 结尾的那些子段所包含的那些 bessie，在末尾拼上 $s[j…i]$ 形成以 $i$ 结尾的那些子段里都被包含。这样子，每个 bessie 在某个子段中出现几次就会被记几次。

然后问题就变成了如何求 $j$，我们定义 $f[i]$ 表示到当前字符，最后一个 bessie 的前 $i$ 个字母中 b 出现的位置，转移方程为：如果当前字符串为 bessie 的第 $i$ 个字母，$f[i] = f[i-1]$。所以最后一个 bessie 中的 b 出现的位置为 $f[6]$（$j = f[6]$）。

这样时间复杂度就是 $\mathcal O(n)$ 的。

code

#include <iostream>
#include <cstdio>
#define int long long

using namespace std;

const int N = 3e5 + 5; 
int n, f[7], ans, dp[N];
string s;

signed main()
{
	cin >> s;
	n = s.size(); 
	s = "#" + s;
	for(int i = 1;i <= n;i++)
	{
		if(s[i] == 'b')
			f[1] = i;
		if(s[i] == 'e')
			f[6] = f[5], f[2] = f[1];
		if(s[i] == 's')
			f[4] = f[3], f[3] = f[2];
		if(s[i] == 'i')
			f[5] = f[4];
		dp[i] = dp[f[6] - 1] + f[6];
	}
	for(int i = 1;i <= n;i++)
		ans += dp[i];
	printf("%lld", ans);
	return 0;
}