信息学奥赛题库- 鏖战字符串

码丁实验室，一站式儿童编程学习产品，寻地方代理合作共赢，微信联系：leon121393608。

【题目描述】

有一天，Abwad决定和nbc鏖战字符串，比的是谁能更快地将一个“量子态的字符串”删除。“量子态的字符串”的每个字符都有一个删除难度$dif[i]$。“量子态的字符串”非常顽固，只能先分割成若干个子串，然后再通过以下两种方式删除：

① 假设子串的所有字符的删除难度之和为$x$，消耗$a×x^2+b$的时间可将子串扔进回收站。

② 若子串中出现次数最多的字符出现的次数不少于$l$次且不多于$r$次，那么采用“量子态的py自动机”算法可以消耗$c×x+d$的时间将子串扔进回收站。

Abwad希望你求出删去每个前缀[$1,i]$的最少用时。

【输入】

第一行七个整数$n，a，b，c，d，l，r$，其中$n$表示字符串的长度。

第二行一行一个长度为$n$的字符串。

第三行一行$n$个整数，表示每个字符的删除难度$dif[i]$。

【输出】

$n$行，每行一个整数$ans$，表示删去前缀$[1,i]$最短的时间。

【输入样例】

5 1 3 1 5 1 1
abwad
1 1 1 1 1

【输出样例】

4
7
8
12
13

【提示】

【样例解释】

以前缀$[1,n]$为例，将串分为$a、bwad$两个子串，用方法①删去第一个子串，用方法②删去第二个子串，用时$1×1+3+1×4+5=13$

【数据规模与约定】

对于所有的数据，满足$n≤100000，1≤a,b,c,d≤233，1≤l,r≤n，0≤dif[i]≤50$,所有字符由小写字母组成。