P9188题解

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