USACO23OPEN-Silver C

题目来源

洛谷： USACO23OPEN-Pareidolia(C)

SPOJ：USACO23OPEN-Pareidolia(C)

题解： USACO23OPEN-Pareidolia(C)

题目背景

是一种现象，你的眼睛倾向于在不存在的图像中看到熟悉的模式，例如在云中看到一张脸。正如你所想象的那样，由于农夫约翰经常与奶牛接触，他经常在日常物品中看到与奶牛相关的图案。例如，如果他看着字符串“”，农夫约翰的眼睛会忽略一些字母，他所看到的只是“”。

题面描述

给定一个字符串，仅包含小写英语字母 $～$ ，的长度不超过。

定义表示把中的若干个字母删去后，形成尽量多个 bessie 相连的形式 (bessiebessiebessieb...)，返回 bessie 的最大数量。如。

对字符串计算是一个有趣的挑战，但农夫约翰想到了一个更有趣的挑战：对的所有子串进行计算函数，并求和。

输入格式

输入一个字符串，该字符串仅包含小写英语字母 $～$ ，其的长度不超过。

输出格式

输出一个整数，表示对的所有子串进行计算函数后的和。

样例

输入数据 1

bessiebessie

输出数据 1

样例1解释

有个子字符串正好包含个 bessie；

有个字符串正好包含个 bessie；

因此总数为。

输入数据 2

abcdefghssijebessie

输出数据 2

数据规模与约定

测试点 $～$ ：输入的长度不超过。
测试点 $～$ ：输入的长度不超过。

题解（Solution）

SPOJ 题解：

首先我们设表示以作为结尾的区间中总共有多少 bessie。

考虑转移。

首先我们需要找到最近的一个 bessie，我们可以考虑设一个表示找到的上一个 bessie 的前项的起始位置。

举个例子，字符串 bessie 就有.

那这个怎么算呢? 我们找到一个字符，先设想其是 bessie 哪一位，设为位，则它的开头显然是

接下来，我们把贡献分成两份，一份是上一个 bessie 的贡献，一份是其他 bessie 的贡献。

后者的贡献我们发现就是，因为往后的字符串与我们当前的这个 bessie 不可以同时出现。

对于当前的字符串，我们发现对于而言都可以包含当前这个 bessie，因此 bessie 总数会增加.

得转移方程：.

而问题问的是所有区间，所有我们需要把它们加起来，即：.

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int N = 301234;
char s[N];
int n,lst[N],f[N],ans;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	cin>>(s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++){//bessie 
		if(s[i]=='b') lst[1]=i;
		if(s[i]=='e') lst[6]=lst[5],lst[2]=lst[1];
		if(s[i]=='s') lst[4]=lst[3],lst[3]=lst[2];
		if(s[i]=='i') lst[5]=lst[4];
		f[i]=f[lst[6]-1]+lst[6];
	}For(i,1,n) ans+=f[i];
	return cout<<ans<<'\n',0;
}