Pareidolia

题目描述

空想性错视（Pareidolia）是一种现象：你的眼睛倾向于在实际上并不存在熟悉图案的图像中看到这些图案——例如在云里看见一张脸。可以想象的是，由于 Farmer John 总是和奶牛待在一起，他经常在日常物品中看到与奶牛相关的图案。比如，当他看字符串 "bqessiyexbesszieb" 时，Farmer John 的眼睛会忽略其中一些字母，而他看到的只有 "bessiexbessieb" ——这个字符串包含两个连续的子串等于 "bessie"。 给定一个长度不超过 $2\cdot 10^5$、只由 a-z 字符组成的字符串，其中每个字符都有一个对应的删除代价。请计算：通过从该字符串中删除零个或多个字符，你最多能得到多少个等于 "bessie" 的连续子串，以及为了达到这个最多数量时所需要删除字符的最小总代价。

输入格式

第一行是字符串。 第二行包含与每个字符对应的删除代价（范围为 $[1,1000]$ 的整数）。

输出格式

输出最多出现次数，以及实现该出现次数所需的最小代价。

besssie
1 1 5 4 6 1 1

1
4

bebesconsiete
6 5 2 3 6 5 7 9 8 1 4 5 1

1
21

besgiraffesiebessibessie
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

2
7

提示

删除第 4 个位置的 's' 后，我们可以让整个字符串变为 "bessie"。第 4 个位置字符的代价是 $4$，因此对于 $1$ 个 "bessie" 实例，我们的答案是代价 $4$，这已经是最优。 通过删除第 5-7 个位置的 "con"，我们可以得到字符串 "bebessiete"，其中间包含 "bessie"。第 5-7 个位置字符的代价为 $5 + 7 + 9 = 21$，因此对于 $1$ 个 "bessie" 实例，我们的答案是代价 $21$，这已经是最优。 该样例满足第二个子任务的限制。 通过删除第 4-10 个位置的 "giraffe"，我们可以得到字符串 "bessiebessibessie"，其开头和结尾各有一个 "bessie"。"giraffe" 有 7 个字符，且所有字符代价为 $1$，因此对于 $2$ 个 "bessie" 实例，我们的答案是代价 $7$，这已经是最优。 评分： 输入 4-5：$N\le 2000$ 输入 6-8：所有代价均为 $1$ 输入 9-17：无额外限制。 题目作者：Benjamin Qi

标签: USACO|2023|Gold

来源

USACO|2023|Gold